Codeforces 1009F 长链剖分优化dp做法
题意:
给出一棵树,设对于一个点, f u , i f_{u,i} fu,i表示距离 u u u为 i i i的点的数量,对于每个点都有一个无限长的序列 [ f u , 0 , f u , 1 . . . . . ] [f_{u,0},f_{u,1}.....] [fu,0,fu,1.....]
找到每个点的序列中的最大值点,如果有多个最大值,那么取点最小的
长链剖分做法:
长链剖分优化 d p dp dp实际上就是一个启发式合并的思路,树上启发式合并一般是对重儿子而言的,每次保留重儿子,即 O ( 1 ) O(1) O(1)继承重儿子,暴力记录轻儿子们,最后的作用是以 O ( n l o g n ) O(nlogn) O(nlogn)统计子树信息。在长链剖分, O ( 1 ) O(1) O(1)继承长儿子,暴力记录短儿子,从链的角度合并为子树,由于每个点只在一条长链上,每个点都被合并一次,有一个优秀的复杂度 O ( n ) O(n) O(n),但有局限性,一般只能合并和深度有关的,而树上启发式合并能做到的更到,但时间也需要更多一些。
设 d p [ u ] [ i ] dp[u][i] dp[u][i]为距离 u u u结点距离为 i i i的儿子个数,那么转移也很简单
d p [ u ] [ i ] = ∑ v ∈ s o n u d p [ v ] [ i − 1 ] dp[u][i]=\sum_{v\in son_{u}} dp[v][i-1] dp[u][i]=v∈sonu∑dp[v][i−1]
显然, d p [ v ] dp[v] dp[v]会被累加进 d p [ u ] dp[u] dp[u],按照启发式合并的思想,应该把深度最深的儿子的子树保留,才能节省时间,不妨利用指针,开一个数组 c n t cnt cnt,选取一个子段来储存 d p [ u ] [ i ] dp[u][i] dp[u][i],令 d p [ u ] dp[u] dp[u]是一个指针,指向 c n t cnt cnt数组上的起点,长度即 m a x 1 [ u ] max1[u] max1[u],长儿子直接在父亲的指针上写信息,父亲 O ( 1 ) O(1) O(1)获得了长儿子信息,即 d p [ s o n [ u ] ] = d p [ u ] + 1 dp[son[u]]=dp[u]+1 dp[son[u]]=dp[u]+1,那么只需要所有长链长度和的 c n t cnt cnt即可,即 n n n的长度,遵循每条长链的所有点共用 c n t cnt cnt的一块,空间复杂度就是 O ( n ) O(n) O(n)的
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct way
{
int to,next;
}edge[2000005];
int cntt,head[1000005];
void add(int u,int v)
{
edge[++cntt].to=v;
edge[cntt].next=head[u];
head[u]=cntt;
}
int cnt[1000005];
int *dp[1000005],ans[1000005],*pp=cnt;
int n,max1[1000005],son[1000005];
void dfs1(int u,int fa)
{
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
dfs1(v,u);
if(max1[v]>max1[son[u]]) son[u]=v;
}
max1[u]=max1[son[u]]+1;
}
void dfs(int u,int fa)
{
dp[u][0]=1;
if(son[u])
{
dp[son[u]]=dp[u]+1;
dfs(son[u],u);
if(dp[son[u]][ans[son[u]]]==1) ans[u]=0;
else ans[u]=ans[son[u]]+1;
}
//max1[u]是u到他的长链底的距离
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa||v==son[u]) continue;
dp[v]=pp; pp+=max1[v];
dfs(v,u);
for(int j=1;j<=max1[v];j++)//暴力记录所有短儿子
{
dp[u][j]+=dp[v][j-1];
if(dp[u][j]>dp[u][ans[u]]) ans[u]=j;
else if(dp[u][j]==dp[u][ans[u]]&&j<ans[u]) ans[u]=j;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v; scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs1(1,0);
dp[1]=pp; pp+=max1[1];//先分配空间再dfs
dfs(1,0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}