CF1709E XOR Tree（set 启发式合并）
enucai
·
·
题解
Analysis
令 a_u 表示 u 的点权，d_u 表示树上 1 到 u 简单路径上所有点的点权异或和。
题目中 u 到 v 的简单路径上的所有点点权异或和 =0 等价于 d_u\oplus d_v\oplus a_{\text{lca}(u,v)}=0。
可以证明如果允许改变 a_u，那么一定可以使以 u 为根的子树中不存在异或和为 0 的简单路径（一种构造方法是令 a_u=2^{u+11^{4514}}）。
考虑对每个点开一个 set，记录其子树中（包括自身）所有点的 d。特别的，若一个点被改变，则其 set 为空 ^{[1]}。
在枚举一个点 rt 的所有儿子时，设现有集合为 S，该儿子的集合为 T，则枚举 T 中的所有元素。设当前枚举元素为 T_i，在 S 中查找是否存在 a_{rt}\oplus T_i，若存在，则子树中一定存在两个点 u,v 满足 d_u\oplus d_v\oplus a_{rt}=0。因此一定要改变 a_{rt}。
复杂度 $O(n^2\log n)$，用 启发式合并 可以使复杂度降低到 $O(n\log^2n)$。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
#define eb emplace_back
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define int long long
int n,res,a[200010],dis[200010];
vector<int> e[200010];
set<int> s[200010];
void dfs(int u,int fa){
bool tmp=0; s[u].insert(dis[u]);
for(int v:e[u]) if(v!=fa){
dis[v]=dis[u]^a[v],dfs(v,u);
if(s[u].size()<s[v].size()) swap(s[u],s[v]);
for(int i:s[v]) if(s[u].find(a[u]^i)!=s[u].end()) tmp=1;
for(int i:s[v]) s[u].insert(i);
}
if(tmp) res++,s[u].clear();
}
signed main(){IOS;
cin>>n;
For(i,1,n) cin>>a[i];
For(i,1,n-1){
int u,v; cin>>u>>v;
e[u].eb(v),e[v].eb(u);
}
dis[1]=a[1];
dfs(1,0);
cout<<res;
}
```