题目链接
题意：给定一棵有点权的树，问最少多少次修改任意点的点权后，能使整棵树的所有简单路径异或和不为0。
首先可以知道，对于一条简单路径来说，一定是修改两个端点的LCA的值最优，直接改为(1<<31)|v[LCA(x,y)]。所以不需要考虑如何修改。
考虑如何维护路径信息。
用set存储子树内所有点到根的异或和，设s[u]表示u为父节点的子树内所有点的值。
假设我们已经算出了子节点中一个节点v对答案的贡献，现在需要计算v并入u后的贡献，也就是计算v节点与u节点子树内其他点对答案的贡献。
计算贡献只需要计算已经维护好贡献的节点即可（可以抽象理解为从左至右维护）。
假设根到点x的异或和值为d[x]，则一条简单路径x到y的异或和值为d[x]^d[y]^d[LCA(x,y)]。
由于此时两点LCA为u，所以只要在u点的set里找子树set的值异或上a[u]即可。
由于直接合并set无法保证复杂度，所以用启发式合并保证复杂度O(nlog2n)。
每个节点如果存在有相同值的情况，就会计算答案，那么这个时候当前点内一定没有贡献，所以要清空set来维护空间复杂度。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,ans,a[N],d[N];
vector<int>G[N];
set<int>s[N];
void dfs(int x,int fa){
int flag=0;
d[x]=d[fa]^a[x];
s[x].insert(d[x]);
for(auto y:G[x])if(y^fa){
dfs(y,x);
if(s[x].size()<s[y].size())swap(s[x],s[y]);
for(auto p:s[y])if(s[x].find(p^a[x])!=s[x].end())flag=1;
for(auto p:s[y])s[x].insert(p);
}
if(flag)++ans,s[x].clear();
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1,x,y;i<n;++i){
scanf("%d%d",&x,&y);
G[x].emplace_back(y),G[y].emplace_back(x);
}
dfs(1,0);
printf("%d\n",ans);
}