2020 CCPC 长春 F（树上启发式合并）

[题目链接](https://vjudge.net/problem/Gym-102832F) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=2e5+5,N=1e6+5; int n,a[M],head[M],nxt[M],ver[M],tot,son[M],siz[M],cnt[N][21][2]; ll ans; void add(int x,int y) { nxt[++tot]=head[x]; head[x]=tot; ver[tot]=y; } void dfs1(int x,int fa) { siz[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa)continue; dfs1(y,x); if(siz[y]>siz[son[x]])son[x]=y; siz[x]+=siz[y]; } } void getval(int x,int fa,int lca) { for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa)continue; getval(y,x,lca); } int d=a[x]^a[lca]; if(d>=N)return ; for(int i=0;i<=20;i++) { int k=(x>>i)&1; ans+=(ll)(1<<i)*cnt[d][i][k^1]; } } void addval(int x,int fa,int val) { for(int i=0;i<=20;i++)cnt[a[x]][i][(x>>i)&1]+=val; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa)continue; addval(y,x,val); } } void dfs2(int x,int fa,int flag) { for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa||y==son[x])continue; dfs2(y,x,0); } if(son[x])dfs2(son[x],x,1); for(int i=0;i<=20;i++)cnt[a[x]][i][(x>>i)&1]++; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa||y==son[x])continue; getval(y,x,x); addval(y,x,1); } if(!flag)addval(x,fa,-1); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n-1;i++) { int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs1(1,0); dfs2(1,0,0); printf("%lld\n",ans); return 0; } ```