随机化选讲例题
题目大意
小 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
对于每个询问输出一行一个正整数，即最小的对称数。
题目分析
异或问题的处理套路，考虑权值的异或和是否为零。
具体来说，就是首先把$1cdots 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]$同理。
其他也没什么细节，反正就是小数据结构练手题吧。
1 #include<bits/stdc++.h> 2 typedef unsigned long long ull; 3 const int maxn = 200035; 4 const int maxm = 400035; 5 const int maxNode = 4000035; 6 7 struct node 8 { 9 int l,r; 10 ull val; 11 }f[maxNode]; 12 ull val[maxn]; 13 int n,m,tot,cnt,rt[maxn],a[maxn],dep[maxn],fat[maxn][21]; 14 int edgeTot,head[maxn],nxt[maxm],edges[maxm]; 15 16 int read() 17 { 18 char ch = getchar(); 19 int num = 0, fl = 1; 20 for (; !isdigit(ch); ch=getchar()) 21 if (ch=='-') fl = -1; 22 for (; isdigit(ch); ch=getchar()) 23 num = (num<<1)+(num<<3)+ch-48; 24 return num*fl; 25 } 26 void addedge(int u, int v) 27 { 28 edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot; 29 edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot; 30 } 31 void update(int &rt, int pre, int l, int r, int c) 32 { 33 rt = ++tot; 34 f[rt] = f[pre], f[rt].val ^= val[c]^val[c-1]; 35 if (l==r) return; 36 int mid = (l+r)>>1; 37 if (c <= mid) update(f[rt].l, f[pre].l, l, mid, c); 38 else update(f[rt].r, f[pre].r, mid+1, r, c); 39 } 40 void dfs(int x, int fa) 41 { 42 fat[x][0] = fa, dep[x] = dep[fa]+1; 43 update(rt[x], rt[fa], 1, cnt, a[x]); 44 for (int i=head[x]; i!=-1; i=nxt[i]) 45 if (edges[i]!=fa) dfs(edges[i], x); 46 } 47 int lca(int u, int v) 48 { 49 if (dep[u] > dep[v]) std::swap(u, v); 50 for (int i=18; i>=0; i--) 51 if (dep[fat[v][i]] >= dep[u]) v = fat[v][i]; 52 if (u==v) return u; 53 for (int i=18; i>=0; i--) 54 if (fat[u][i]!=fat[v][i]) u = fat[u][i], v = fat[v][i]; 55 return fat[u][0]; 56 } 57 void query(int l, int r, int u, int v, int p, int q) 58 { 59 if (l==r) printf("%d ",l); 60 else{ 61 int mid = (l+r)>>1; 62 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-1])) 63 query(l, mid, f[u].l, f[v].l, f[p].l, f[q].l); 64 else query(mid+1, r, f[u].r, f[v].r, f[p].r, f[q].r); 65 } 66 } 67 int main() 68 { 69 srand(3627); 70 for (int i=1; i<=200000; i++) 71 val[i] = (1ll*rand()*rand()*rand()+1ll*rand()*rand())^val[i-1]; 72 for (int T=read(); T; --T) 73 { 74 memset(head, -1, sizeof head); 75 n = read(), m = read(), cnt = tot = edgeTot = 0; 76 for (int i=1; i<=n; i++) a[i] = read(), cnt = std::max(cnt, a[i])+1; 77 for (int i=1; i<n; i++) addedge(read(), read()); 78 dfs(1, 0); 79 for (int j=1; j<=18; j++) 80 for (int i=1; i<=n; i++) 81 fat[i][j] = fat[fat[i][j-1]][j-1]; 82 for (; m; --m) 83 { 84 int u = read(), v = read(), anc = lca(u, v); 85 query(1, cnt, rt[u], rt[v], rt[anc], rt[fat[anc][0]]); 86 } 87 } 88 return 0; 89 }
END