Codeforces 1009F 长链剖分优化dp做法

题意：

给出一棵树，设对于一个点，$f_{u,i}$表示距离$u$为$i$的点的数量，对于每个点都有一个无限长的序列$[f_{u,0},f_{u,1}.....]$

找到每个点的序列中的最大值点，如果有多个最大值，那么取点最小的

长链剖分做法：

长链剖分优化$dp$实际上就是一个启发式合并的思路，树上启发式合并一般是对重儿子而言的，每次保留重儿子，即$O(1)$继承重儿子，暴力记录轻儿子们，最后的作用是以$O(nlogn)$统计子树信息。在长链剖分，$O(1)$继承长儿子，暴力记录短儿子，从链的角度合并为子树，由于每个点只在一条长链上，每个点都被合并一次，有一个优秀的复杂度$O(n)$，但有局限性，一般只能合并和深度有关的，而树上启发式合并能做到的更到，但时间也需要更多一些。

设$dp[u][i]$为距离$u$结点距离为$i$的儿子个数，那么转移也很简单

$$dp[u][i]=\sum _{v\in so{n}_u}dp[v][i-1]$$

显然，$dp[v]$会被累加进$dp[u]$，按照启发式合并的思想，应该把深度最深的儿子的子树保留，才能节省时间，不妨利用指针，开一个数组$cnt$，选取一个子段来储存$dp[u][i]$，令$dp[u]$是一个指针，指向$cnt$数组上的起点，长度即$max1[u]$，长儿子直接在父亲的指针上写信息，父亲$O(1)$获得了长儿子信息，即$dp[son[u]]=dp[u]+1$，那么只需要所有长链长度和的$cnt$即可，即$n$的长度，遵循每条长链的所有点共用$cnt$的一块，空间复杂度就是$O(n)$的

#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73