cf1709E. XOR Tree
贪心是显然的，关键是如何合并两棵子树的信息，可以采用启发式合并。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=2e5+5;
int n,a[N],x,y,b[N];
int head[N],to[N*2],nex[N*2],tot,ans;
set<int> c[N];
void add(int x,int y){
to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
b[x]^=a[x];
for (int i=head[x];i;i=nex[i]){
int v=to[i];
if (v==y) continue;
b[v]^=b[x];
dfs(v,x);
}
}
void calc(int x,int y){
c[x].insert(b[x]);
bool flag=0;
for (int i=head[x];i;i=nex[i]){
int v=to[i];
if (v==y) continue;
calc(v,x);
if (c[x].size() < c[v].size()) c[x].swap(c[v]);
for (auto j:c[v]) {
if (c[x].find(j^a[x])!=c[x].end()) {
flag=1;
}
}
for (auto j:c[v]) {
c[x].insert(j);
}
}
if (flag) {
ans++;
c[x].clear();
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
fo(i,1,n-1) {
scanf("%d %d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
calc(1,0);
printf("%d",ans);
return 0;
}