树链剖分之长链剖分
给定一棵树,对于每个点找出一个距离k,使得在该子树下与该点距离为k的点数最多
f[u][i]表示u节点距离为i的点数, $ f_{u,i}= \sum f_{v,i-1} $- 直接转移为 $ O(n^2) $
考虑优化,长链剖分,类似于启发式合并,定义深度最大的点为son[u] - 对于一条长链上的点使用同一块内存空间
f[son[u]]=f[u]+1即向右移一次(假设u的第二维的头为1,向右移一位son[u]的第二维的头变成2,因此更新f[son[u]][i]即为更新f[u][i+1]) - 除重儿子外的轻儿子,暴力转移(转移次数为
dep[v]),总深度为n因此总复杂度为$ O(n) $
cpp
int dep[N],son[N],ans[N];
int buf[N],*f[N],*it=buf;
vector<int> adj[N];
void dfs1(int u,int fa){
for(auto v:adj[u]){
if(v==fa)continue;
dfs1(v,u);
if(dep[son[u]]<dep[v])son[u]=v;
}
dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int fa){
f[u][0]=1;
if(!son[u])return;
f[son[u]]=f[u]+1;
dfs2(son[u],u);
ans[u]=ans[son[u]]+1;
if(f[u][ans[u]]==1)ans[u]=0;
for(auto v:adj[u]){
if(v==fa||v==son[u])continue;
f[v]=it,it+=dep[v];
dfs2(v,u);
for(int i=1;i<=dep[v];i++){
f[u][i]+=f[v][i-1];
if(f[u][i]>f[u][ans[u]]||(f[u][i]==f[u][ans[u]]&&i<ans[u]))ans[u]=i;
}
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs1(1,0);
f[1]=it,it+=dep[1];
dfs2(1,0);
for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
}