这道题用到了dsu（Disjoint Set Union） on tree，树上启发式合并。
先看了CF的官方英文题解，又看了看zwz大佬的题解，差不多理解了dsu on tree的算法。
但是时间复杂度有点玄学，问了一下zwz大佬才懂了为什么是nlogn。
先考虑暴力n^2的算法。
显然对于某个点，搜一遍它的子树，就能得到这个点的答案。这一步是O（n）的。
每个点都这么搞一遍，就是O（n^2）的暴力做法。
但是这个暴力做法有一点不足，子节点的答案没有应用到父节点的计算中，白白浪费时间重算一遍。
考虑优化，类似树链剖分，找出子树最大的儿子称作重儿子，把它的答案留着，这样计算父节点时就不用搜这个重儿子了。
显然保留子树最大的儿子的信息，能够节约最多的时间。
但是如果计算完重儿子的答案，保留了信息，再计算别的儿子的答案，已保留的信息会对当前的计算产生干扰。
所以我们先计算轻儿子，最后计算重儿子。
如果是轻儿子，更新答案计算后，暴力再改回去。
如果是重儿子，就留着。
计算完所有儿子的答案后，最后计算当前点。
只需要加上轻儿子的信息就好。重儿子的信息已经留着了，不用再加了。
下面是zwz大佬对于dsu on tree时间复杂度的证明：
每个节点只会在祖先节点的计算中被搜到。
而且只有它到它父亲是轻边的时候才会搜一遍。
所以每个点的计算次数是它到根的轻边数量，为logn。
所以总时间复杂度是nlogn。
感觉dsu也是挺暴力的，每次留一个，居然时间上优化了很多。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1000005
using namespace std; int n;
int hd[MAXN],nx[MAXN<<],to[MAXN<<],ec;
int dep[MAXN],sz[MAXN],ans[MAXN],cnt[MAXN]; void edge(int af,int at)
{
to[++ec]=at;
nx[ec]=hd[af];
hd[af]=ec;
} void pre(int p,int fa)
{
sz[p]=;
dep[p]=dep[fa]+;
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa)continue;
pre(to[i],p);
sz[p]+=sz[to[i]];
}
} struct data
{
int d,v;
friend bool operator<(data q,data w)
{
if(q.v==w.v)return q.d>w.d;
return q.v<w.v;
}
}; priority_queue<data>qq; void add(int p,int fa)
{
cnt[dep[p]]++;
data neo={dep[p],cnt[dep[p]]};
qq.push(neo);
for(int i=hd[p];i;i=nx[i])if(to[i]!=fa)add(to[i],p);
} void del(int p,int fa)
{
cnt[dep[p]]--;
for(int i=hd[p];i;i=nx[i])if(to[i]!=fa)del(to[i],p);
} void dfs(int p,int fa,int stay)
{
int son=,mx=-;
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa)continue;
if(mx<sz[to[i]])mx=sz[to[i]],son=to[i];
}
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa||to[i]==son)continue;
dfs(to[i],p,);
}
if(son)dfs(son,p,);
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa||to[i]==son)continue;
add(to[i],p);
}
cnt[dep[p]]++;
data neo={dep[p],cnt[dep[p]]};
qq.push(neo);
ans[p]=qq.top().d-dep[p];
if(!stay)
{
del(p,fa);
while(!qq.empty())qq.pop();
}
} int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edge(x,y);
edge(y,x);
}
pre(,);
dfs(,,);
for(int i=;i<=n;i++)printf("%d\n",ans[i]);
return ;
}
CF1009F Dominant Indices
P.S. 调试的时候改小了数组，提交的时候忘改回去了......改回去之后直接A掉了......有点桑心哈哈哈