解题：CF1009 Dominant Indices

题面

长链剖分模板题

只能按深度统计，同时比DSU on tree难理解一些，但是复杂度少个log

对每个点抓出向下延伸最长的儿子叫做长儿子。在合并时用指针继承信息，对于长儿子O(1)继承，其他儿子暴力

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int len[N],imp[N],ans[N];

 int p[N],noww[*N],goal[*N];

 int mem[N],*pts[N],*fpt=mem+;

 int n,t1,t2,cnt;

 void Link(int f,int t)

 {

     noww[++cnt]=p[f];

     goal[cnt]=t,p[f]=cnt;

 }

 void DFS(int nde,int fth,int dth)

 {

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             DFS(goal[i],nde,dth+);

             if(len[goal[i]]>len[imp[nde]])

                 imp[nde]=goal[i];

         }

     len[nde]=len[imp[nde]]+;

 }

 void Getans(int nde,int fth)

 {

     pts[nde][]=;

     if(imp[nde])

     {

         pts[imp[nde]]=pts[nde]+;

         Getans(imp[nde],nde),ans[nde]=ans[imp[nde]]+;

     }

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth&&goal[i]!=imp[nde])

         {

             pts[goal[i]]=fpt,fpt+=len[goal[i]],Getans(goal[i],nde);

             for(int j=;j<=len[goal[i]];j++)

             {

                 pts[nde][j]+=pts[goal[i]][j-];

                 int b1=(j<=ans[nde]&&pts[nde][j]>=pts[nde][ans[nde]]);

                 int b2=(j>ans[nde]&&pts[nde][j]>pts[nde][ans[nde]]);

                 if(b1||b2) ans[nde]=j;

             }

         }

     if(pts[nde][ans[nde]]==) ans[nde]=;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<n;i++)

     {

         scanf("%d%d",&t1,&t2);

         Link(t1,t2),Link(t2,t1);

     }

     DFS(,,),pts[]=fpt,fpt+=len[];

     Getans(,);

     for(int i=;i<=n;i++)

         printf("%d\n",ans[i]);

     return ;

 }