思路来源
https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9
https://blog.csdn.net/litble/article/details/87965999
知识点整理
长链剖分，用于维护子树中只与深度有关的信息，多用于静态
从任何一个点往上跳到根，最多经过条不同的长链。
长链剖分，顾名思义，每个点维护子树中最长的那一条链，
[l[x],l[x]+len[x]-1]是其长链区间，到l[x]的偏移量也确定了它的深度
和dsu on tree类似，但若干条链分别占用不同位置的数组空间，只有相同链的内存共用，
所以不用像dsu on tree那样清空内存，所以预处理长链长度之后，只需要三步
①搜长儿子，继承长儿子的答案
②把短儿子往长儿子上挂，计算短儿子的答案
③把自己这个节点挂上去
由于若干条长链不交，每个点在向上合并的时候，只会作为短链出现在一条链里，所以是O(n)的
似乎还是指针版的略快一点，然而习惯用数组下标写……
题目
n(n<=1e6)个点的树，
对于每个点，求其子树中出现节点最多的深度d，
如果存在多个深度，它们的节点个数相同，则返回最小的哪个
题解
搞个裸题，长链剖分合并，
首先继承长链答案，然后短链合并的时候，如果可更新则更新
最后check一下这棵子树的根的深度，判断其是否能更新答案
代码
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e6+10;
int son[N],len[N];//长儿子
int n,u,v;
int l[N],r[N],dfn;//长链的dfs序区间段
int sum[N],ans[N];
vector<int>e[N];
void dfs1(int u,int fa){
for(int v:e[u]){
if(v==fa)continue;
dfs1(v,u);
if(!son[u] || len[son[u]]<len[v]){
son[u]=v;
}
}
len[u]=len[son[u]]+1;
}
void dfs2(int u,int fa){
l[u]=++dfn;
r[u]=l[u]+len[u]-1;
if(son[u]){
dfs2(son[u],u);
ans[u]=ans[son[u]]+1;//答案来自长儿子
}
for(int v:e[u]){
if(v==fa || v==son[u])continue;
dfs2(v,u);
//答案来自短儿子
for(int j=l[v],k=1;j<=r[v];++j,++k){
sum[l[u]+k]+=sum[j];
if((k>ans[u] && sum[l[u]+k]>sum[l[u]+ans[u]]) || (k<ans[u] && sum[l[u]+k]>=sum[l[u]+ans[u]])){
ans[u]=k;
}
}
}
sum[l[u]]++;
if(sum[l[u]]>=sum[l[u]+ans[u]]){
ans[u]=0;
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;++i){
scanf("%d%d",&u,&v);
e[u].pb(v);e[v].pb(u);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;++i){
printf("%d\n",ans[i]);
}
return 0;
}
