package main
import (
"bufio"
"fmt"
"math/bits"
"os"
"sort"
)
type SegTree struct {
n int
tree []int
}
func NewSegTree(arr []int) *SegTree {
n := len(arr)
st := &SegTree{n: n, tree: make([]int, 4*n)}
st.build(1, 0, n-1, arr)
return st
}
func (st *SegTree) build(id, l, r int, arr []int) {
if l == r {
st.tree[id] = arr[l]
return
}
m := (l + r) >> 1
st.build(id<<1, l, m, arr)
st.build(id<<1|1, m+1, r, arr)
st.tree[id] = st.tree[id<<1] | st.tree[id<<1|1]
}
func (st *SegTree) QueryOr(l, r int) int {
if l > r {
return 0
}
return st.qOr(1, 0, st.n-1, l, r)
}
func (st *SegTree) qOr(id, l, r, ql, qr int) int {
if ql <= l && r <= qr {
return st.tree[id]
}
m := (l + r) >> 1
res := 0
if ql <= m {
res |= st.qOr(id<<1, l, m, ql, qr)
}
if qr > m {
res |= st.qOr(id<<1|1, m+1, r, ql, qr)
}
return res
}
func (st *SegTree) FindFirstLeft(l, r int, bit int) int {
return st.ffl(1, 0, st.n-1, l, r, bit)
}
func (st *SegTree) ffl(id, l, r, ql, qr, bit int) int {
if r < ql || l > qr {
return -1
}
if ((st.tree[id] >> bit) & 1) == 0 {
return -1
}
if l == r {
return l
}
m := (l + r) >> 1
res := st.ffl(id<<1, l, m, ql, qr, bit)
if res != -1 {
return res
}
return st.ffl(id<<1|1, m+1, r, ql, qr, bit)
}
func (st *SegTree) FindFirstRight(l, r int, bit int) int {
return st.ffr(1, 0, st.n-1, l, r, bit)
}
func (st *SegTree) ffr(id, l, r, ql, qr, bit int) int {
if r < ql || l > qr {
return -1
}
if ((st.tree[id] >> bit) & 1) == 0 {
return -1
}
if l == r {
return l
}
m := (l + r) >> 1
res := st.ffr(id<<1|1, m+1, r, ql, qr, bit)
if res != -1 {
return res
}
return st.ffr(id<<1, l, m, ql, qr, bit)
}
type FastScanner struct {
r *bufio.Reader
}
func NewFastScanner() *FastScanner {
return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}
func (fs *FastScanner) NextInt() int {
sign := 1
val := 0
c, _ := fs.r.ReadByte()
for (c < '0' || c > '9') && c != '-' {
c, _ = fs.r.ReadByte()
}
if c == '-' {
sign = -1
c, _ = fs.r.ReadByte()
}
for c >= '0' && c <= '9' {
val = val*10 + int(c-'0')
c, _ = fs.r.ReadByte()
}
return sign * val
}
func main() {
in := NewFastScanner()
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
t := in.NextInt()
for ; t > 0; t-- {
n := in.NextInt()
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = in.NextInt()
}
adj := make([][]int, n)
for i := 0; i < n-1; i++ {
u := in.NextInt() - 1
v := in.NextInt() - 1
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
parent := make([]int, n)
depth := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = -1
}
order := make([]int, 0, n)
stack := make([]int, 0, n)
stack = append(stack, 0)
parent[0] = 0
depth[0] = 0
for len(stack) > 0 {
u := stack[len(stack)-1]
stack = stack[:len(stack)-1]
order = append(order, u)
for _, v := range adj[u] {
if v == parent[u] {
continue
}
parent[v] = u
depth[v] = depth[u] + 1
stack = append(stack, v)
}
}
size := make([]int, n)
heavy := make([]int, n)
for i := 0; i < n; i++ {
heavy[i] = -1
}
for i := n - 1; i >= 0; i-- {
u := order[i]
size[u] = 1
maxsz := 0
for _, v := range adj[u] {
if v == parent[u] {
continue
}
size[u] += size[v]
if size[v] > maxsz {
maxsz = size[v]
heavy[u] = v
}
}
}
head := make([]int, n)
pos := make([]int, n)
inv := make([]int, n)
time := 0
type pair struct{ u, h int }
stk := make([]pair, 0, n)
stk = append(stk, pair{0, 0})
for len(stk) > 0 {
p := stk[len(stk)-1]
stk = stk[:len(stk)-1]
u := p.u
h := p.h
for v := u; v != -1; v = heavy[v] {
head[v] = h
pos[v] = time
inv[time] = v
time++
for _, c := range adj[v] {
if c == parent[v] || c == heavy[v] {
continue
}
stk = append(stk, pair{c, c})
}
}
}
base := make([]int, n)
for i := 0; i < n; i++ {
base[pos[i]] = a[i]
}
seg := NewSegTree(base)
type Seg struct {
l, r int
dir int // +1 left->right, -1 right->left
orv int
len int
}
getPathSegs := func(u, v int) ([]Seg, int, []int, []int) {
upParts := make([]Seg, 0, 32)
downParts := make([]Seg, 0, 32)
uu, vv := u, v
for head[uu] != head[vv] {
if depth[head[uu]] >= depth[head[vv]] {
upParts = append(upParts, Seg{l: pos[head[uu]], r: pos[uu], dir: -1})
uu = parent[head[uu]]
} else {
downParts = append(downParts, Seg{l: pos[head[vv]], r: pos[vv], dir: +1})
vv = parent[head[vv]]
}
}
segs := make([]Seg, 0, len(upParts)+len(downParts)+1)
for i := 0; i < len(upParts); i++ {
segs = append(segs, upParts[i])
}
if depth[uu] >= depth[vv] {
segs = append(segs, Seg{l: pos[vv], r: pos[uu], dir: -1})
} else {
segs = append(segs, Seg{l: pos[uu], r: pos[vv], dir: +1})
}
for i := len(downParts) - 1; i >= 0; i-- {
segs = append(segs, downParts[i])
}
total := 0
prefix := make([]int, len(segs)+1)
for i := 0; i < len(segs); i++ {
if segs[i].l <= segs[i].r {
segs[i].len = segs[i].r - segs[i].l + 1
} else {
segs[i].len = segs[i].l - segs[i].r + 1
}
segs[i].orv = seg.QueryOr(min(segs[i].l, segs[i].r), max(segs[i].l, segs[i].r))
total += segs[i].len
prefix[i+1] = total
}
// suffix for reversed distance from y
suffix := make([]int, len(segs)+1)
for i := len(segs) - 1; i >= 0; i-- {
suffix[i] = suffix[i+1] + segs[i].len
}
return segs, total, prefix, suffix
}
q := in.NextInt()
for ; q > 0; q-- {
x := in.NextInt() - 1
y := in.NextInt() - 1
segs, totalNodes, prefix, suffix := getPathSegs(x, y)
fullOr := 0
for i := 0; i < len(segs); i++ {
fullOr |= segs[i].orv
}
B := bits.OnesCount(uint(fullOr))
events := make([][2]int, 0, 64)
for b := 0; b < 31; b++ {
if ((fullOr >> b) & 1) == 0 {
continue
}
// find first occurrence from x
dL := 0
found := false
for i := 0; i < len(segs); i++ {
if ((segs[i].orv >> b) & 1) == 0 {
continue
}
l, r := segs[i].l, segs[i].r
var idx int
if segs[i].dir == +1 {
if l <= r {
idx = seg.FindFirstLeft(l, r, b)
} else {
idx = seg.FindFirstLeft(r, l, b)
}
if l > r {
// reversed l,r in query; idx is in [r,l]
// map to original interval indices
// but offset formula uses l as min; keep consistent by rebuilding l=min(l,r)
l2 := min(l, r)
dL = prefix[i] + (idx - l2)
found = true
break
}
dL = prefix[i] + (idx - l)
} else { // dir == -1
if l <= r {
idx = seg.FindFirstRight(l, r, b)
dL = prefix[i] + (r - idx)
} else {
idx = seg.FindFirstRight(r, l, b)
// original interval [l,r] with l>r, dir -1, nodes count len = l-r+1
// when querying [r,l], rightmost idx corresponds to original closer to r side (which is smaller index in original)
// offset from start of segment in original order (from l down to r) equals (l - idx)
dL = prefix[i] + (l - idx)
}
}
found = true
break
}
if !found {
// should not happen since bit is in fullOr
continue
}
// find last occurrence from y (scan reversed)
dFromY := 0
found = false
for i := len(segs) - 1; i >= 0; i-- {
if ((segs[i].orv >> b) & 1) == 0 {
continue
}
l, r := segs[i].l, segs[i].r
var idx int
if segs[i].dir == +1 {
// reversed direction: search from right -> left
if l <= r {
idx = seg.FindFirstRight(l, r, b)
dFromY = suffix[i+1] + (r - idx)
} else {
idx = seg.FindFirstRight(r, l, b)
// original had l>r with dir +1? impossible; dir +1 implies l<=r
dFromY = suffix[i+1] + (l - idx)
}
} else { // dir == -1
// reversed direction: search from left -> right
if l <= r {
idx = seg.FindFirstLeft(l, r, b)
dFromY = suffix[i+1] + (idx - l)
} else {
idx = seg.FindFirstLeft(r, l, b)
// original l>r, dir -1 valid
// when querying [r,l], leftmost idx corresponds to original closer to l side
// distance from y side counts from end of path, which aligns with segments after i plus offset within this segment from its end (original r side)
// For original dir -1, reversed offset equals idx - r
dFromY = suffix[i+1] + (idx - r)
}
}
found = true
break
}
if !found {
continue
}
dR := (totalNodes - 1) - dFromY
events = append(events, [2]int{dL, 1})
events = append(events, [2]int{dR + 1, -1})
}
if len(events) == 0 {
fmt.Fprintln(out, B)
continue
}
sort.Slice(events, func(i, j int) bool {
if events[i][0] == events[j][0] {
return events[i][1] > events[j][1]
}
return events[i][0] < events[j][0]
})
cur := 0
best := 0
idx := 0
for idx < len(events) {
p := events[idx][0]
sum := 0
for idx < len(events) && events[idx][0] == p {
sum += events[idx][1]
idx++
}
cur += sum
if p < totalNodes && cur > best {
best = cur
}
}
fmt.Fprintln(out, B+best)
}
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}