题目大意
小 Q 认为，偶数具有对称美，而奇数则没有。给定一棵 n 个点的树，任意两点之间有且仅有一条直接或间接路径。这些点编号依次为 1 到 n，其中编号为 i 的点上有一个正整数 ai。
定义集合 S(u, v) 为 u 点到 v 点的唯一最短路径上经过的所有点 x(包括 u 和 v) 对应的正整数 ax 的集合。小 Q 将在 m 个 S(u, v) 中寻找最小的对称数。因为偶数具有对称美，所以对称数是指那些出 现了偶数次 (包括 0 次) 的正整数。
请写一个程序，帮助小 Q 找到最小的对称数。
Input
第一行包含一个正整数 T (1 ≤ T ≤ 10)，表示测试数据的组数。
每组数据第一行包含两个正整数 n, m(1 ≤ n, m ≤ 200000)，分别表示点数和询问数。
第二行包含 n 个正整数 a1, a2, ..., an(1 ≤ ai ≤ 200000)，依次表示每个点上的数字。
接下来 n − 1 行，每行两个正整数 ui,vi(1 ≤ ui,vi ≤ n,ui ̸= vi)，表示一条连接 ui 和 vi 的双向树 边。
接下来 m 行，每行两个正整数 ui, vi(1 ≤ ui, vi ≤ n)，依次表示每个询问。
Output
对于每个询问输出一行一个正整数，即最小的对称数。
题目分析
异或问题的处理套路，考虑权值的异或和是否为零。
具体来说，就是首先把$1\cdots 200000$各自随机一个ull的权值$val_i$，再使用树上建的主席树二分检查查询的路径$(u,v)$中的权值$[l,r]$：若$[l,mid]$的权值异或不等于$val_l \oplus val_{l+1} \cdots val_{mid}$，说明$[l,mid]$内至少有一个数出现了偶数次，那么就向$[l,mid]$层递归；$[mid+1,r]$同理。
其他也没什么细节，反正就是小数据结构练手题吧。
#include<bits/stdc++.h>
typedef unsigned long long ull;
const int maxn = ;
const int maxm = ;
const int maxNode = ; struct node
{
int l,r;
ull val;
}f[maxNode];
ull val[maxn];
int n,m,tot,cnt,rt[maxn],a[maxn],dep[maxn],fat[maxn][];
int edgeTot,head[maxn],nxt[maxm],edges[maxm]; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
void addedge(int u, int v)
{
edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
}
void update(int &rt, int pre, int l, int r, int c)
{
rt = ++tot;
f[rt] = f[pre], f[rt].val ^= val[c]^val[c-];
if (l==r) return;
int mid = (l+r)>>;
if (c <= mid) update(f[rt].l, f[pre].l, l, mid, c);
else update(f[rt].r, f[pre].r, mid+, r, c);
}
void dfs(int x, int fa)
{
fat[x][] = fa, dep[x] = dep[fa]+;
update(rt[x], rt[fa], , cnt, a[x]);
for (int i=head[x]; i!=-; i=nxt[i])
if (edges[i]!=fa) dfs(edges[i], x);
}
int lca(int u, int v)
{
if (dep[u] > dep[v]) std::swap(u, v);
for (int i=; i>=; i--)
if (dep[fat[v][i]] >= dep[u]) v = fat[v][i];
if (u==v) return u;
for (int i=; i>=; i--)
if (fat[u][i]!=fat[v][i]) u = fat[u][i], v = fat[v][i];
return fat[u][];
}
void query(int l, int r, int u, int v, int p, int q)
{
if (l==r) printf("%d\n",l);
else{
int mid = (l+r)>>;
if ((f[f[u].l].val^f[f[v].l].val^f[f[p].l].val^f[f[q].l].val)!=(val[mid]^val[l-]))
query(l, mid, f[u].l, f[v].l, f[p].l, f[q].l);
else query(mid+, r, f[u].r, f[v].r, f[p].r, f[q].r);
}
}
int main()
{
srand();
for (int i=; i<=; i++)
val[i] = (1ll*rand()*rand()*rand()+1ll*rand()*rand())^val[i-];
for (int T=read(); T; --T)
{
memset(head, -, sizeof head);
n = read(), m = read(), cnt = tot = edgeTot = ;
for (int i=; i<=n; i++) a[i] = read(), cnt = std::max(cnt, a[i])+;
for (int i=; i<n; i++) addedge(read(), read());
dfs(, );
for (int j=; j<=; j++)
for (int i=; i<=n; i++)
fat[i][j] = fat[fat[i][j-]][j-];
for (; m; --m)
{
int u = read(), v = read(), anc = lca(u, v);
query(, cnt, rt[u], rt[v], rt[anc], rt[fat[anc][]]);
}
}
return ;
}
END