ICPC 2019 银川 E（长链剖分）

[题目链接](https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-42385) ------------ 考虑如何求解$\sum_{i=1}^n\sum_{j=i+1}^n (a_i \bigoplus a_j)^2$ $=\sum_{i=1}^n\sum_{j=i+1}^n( a_{i,0} \bigoplus a_{j,0}+ a_{i,1} \bigoplus a_{j,1}++...a_{i,29} \bigoplus a_{j,29})^2$ $=\sum_{i=1}^n\sum_{j=i+1}^n \sum_{k1=0}^{29}\sum_{k2=0}^{29}(a_{i,k1} \bigoplus a_{j,k1})(a_{i,k2} \bigoplus a_{j,k2})2^{k1+k2}$ $=\sum_{k1=0}^{29}\sum_{k2=0}^{29} 2^{k1+k2} \sum_{i=1}^n\sum_{j=i+1}^n [a_{i,k1} \neq a_{j,k1}][a_{i,k2} \neq a_{j,k2}]$ 长链剖分处理后缀和 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int M=2e5+5; int n,k,a[M],head[M],nxt[M],ver[M],tot,len[M],top[M],son[M],m,id[M],c[M][4]; ull ans[M]; void add(int x,int y) { nxt[++tot]=head[x]; head[x]=tot; ver[tot]=y; } void dfs1(int x) { len[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; dfs1(y); if(len[y]+1>len[x]) { len[x]=len[y]+1; son[x]=y; } } for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y!=son[x])top[y]=1; } } int pre(int x,int v) { if(len[x]-2<k)return c[id[x]][v]; return c[id[x]][v]-c[id[x]+k+1][v]; } void dfs2(int x,int k1,int k2) { if(top[x]) { id[x]=m+1; m+=len[x]; } int b=0; if((a[x]>>k1)&1)b|=1; if((a[x]>>k2)&1)b|=2; c[id[x]][b]++; if(son[x]) { id[son[x]]=id[x]+1; dfs2(son[x],k1,k2); for(int i=0;i<=3;i++) c[id[x]][i]+=c[id[son[x]]][i]; } for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==son[x])continue; dfs2(y,k1,k2); for(int j=0;j<=3;j++) c[id[x]][j]+=c[id[y]][j]; for(int l=0;l<len[y];l++) for(int j=0;j<=3;j++) c[id[x]+l+1][j]+=c[id[y]+l][j]; } for(int i=0;i<=1;i++) { int t=(k1!=k2?2:1); ans[x]+=((ull)t*pre(x,i)*pre(x,i^3))<<(k1+k2); } } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=2;i<=n;i++) { int fa;scanf("%d",&fa); add(fa,i); } top[1]=1; dfs1(1); for(int k1=0;k1<30;k1++) for(int k2=k1;k2<30;k2++) { m=0; for(int i=1;i<=n;i++) for(int j=0;j<=3;j++) c[i][j]=0; dfs2(1,k1,k2); } for(int i=1;i<=n;i++)printf("%llu\n",ans[i]); return 0; } ```