cf860E Arkady and A Nobody-men (树剖)

容易得出，如果我们按照深度一层一层地做，做完一层后，这层某个点的答案就是它的祖先们的子树大小（统计大小时不包括树根）

由于我太菜了不会别的方法，虽然N是5e5的，还是只好用一个树剖（树状数组降常数）水过去了

就是统计到某个点的时候把它的父亲到根+1

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=5e5+;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 int dfn[maxn],id[maxn],tot,fa[maxn],dep[maxn],top[maxn],bot[maxn];

 ll tr[maxn],itr[maxn],ans[maxn];

 int eg[maxn][],egh[maxn],ect,N,wson[maxn],siz[maxn];

 int bfn[maxn],qt,qh,root;

 inline void adeg(int a,int b){

     eg[++ect][]=b,eg[ect][]=egh[a];egh[a]=ect;

 }

 void dfs1(int x){

     // printf("!%d %d\n",x,fa[x]);

     siz[x]=;int mm=;

     for(int i=egh[x];i;i=eg[i][]){

         int b=eg[i][];

         dep[b]=dep[x]+;dfs1(b);

         if(mm<siz[b]) mm=siz[b],wson[x]=b;

         siz[x]+=siz[b];

     }

 }

 void dfs2(int x){

     dfn[x]=++tot,id[tot]=x;

     top[x]=(x==wson[fa[x]])?top[fa[x]]:x;

     if(wson[x]) dfs2(wson[x]);

     else bot[top[x]]=x;

     for(int i=egh[x];i;i=eg[i][]){

         int b=eg[i][];

         if(b==wson[x]) continue;

         dfs2(b);

     }

 }

 inline int lowbit(int x){return x&(-x);}

 inline void add(int tp,int bt,int x,int y){

     x-=tp;ll iy=y*x;

     for(;x<=bt-tp;x+=lowbit(x)) tr[x+tp]+=y,itr[x+tp]+=iy;

 }

 inline ll query(int tp,int x){

     ll re=;x-=tp;int n=x;

     for(;x;x-=lowbit(x)) re+=(n+)*tr[x+tp]-itr[x+tp];

     return re;

 }

 inline void tradd(int x){

     while(x){

         add(dfn[top[x]]-,dfn[bot[top[x]]],dfn[top[x]],);

         add(dfn[top[x]]-,dfn[bot[top[x]]],dfn[x]+,-);

         x=fa[top[x]];

     }

 }

 inline ll trque(int x){

     ll re=;

     while(x){

         // printf("!%d %d %d\n",dfn[x],dfn[top[x]],dfn[bot[top[x]]]);

         re+=query(dfn[top[x]]-,dfn[x]);

         x=fa[top[x]];

     }return re;

 }

 inline void bfs(){

     bfn[qh=qt=]=root;

     while(qh<=qt){

         int p=bfn[qh++];

         for(int i=egh[p];i;i=eg[i][]){

             // printf("%d %d\n",i,eg[i][0]);

             bfn[++qt]=eg[i][];

         }

     }

     int lst=;

     for(int i=;i<=qt;i++){

         for(;dep[bfn[lst]]!=dep[bfn[i]];lst++)

             ans[bfn[lst]]=trque(fa[bfn[lst]]);

         tradd(fa[bfn[i]]);

     }

     for(;lst<=qt;lst++)

         ans[bfn[lst]]=trque(fa[bfn[lst]]);

 }

 int main(){

     //freopen("","r",stdin);

     int i,j,k;

     N=rd();

     for(i=;i<=N;i++){

         fa[i]=rd();

         if(fa[i]) adeg(fa[i],i);

         else root=i;

     }

     dep[]=root;dfs1(root);dfs2(root);

     bfs();

     for(i=;i<=N;i++)

         printf("%I64d ",ans[i]);

     return ;

 }