Eternity

Until The End

树型dp

发表于 更新于 分类于 ，
本文字数： 9.9k 阅读时长 ≈ 9 分钟

“父承子业。”

简单来说就是在一棵树上进行 $dp$ 操作。一般是从子节点转移到父节点。初始化为叶节点。

其可扩展性十分高。所以没有固定模板而言。但一般实现方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dp(int x,int last)		//当前节点以及其父节点
{
    dp[x]=/*something*/;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;		//不可回溯
        dp(v,x);
        /*
        	some Codes;
        */
	}
    /*
    	some Code;
    */
}
int main()
{
    dp(Rt,-1);
}

基本操作

求树的直径

两种方法

  1. 两遍 $bfs$ 或 $dfs$ 。第一次从任意点开始，找到该点能到达的最远距离，第二次从找到的点出发，再次找最远点。这两点就是树的直径。复杂度 $O(2n)$ 。
  2. 考虑树型 $dp$ 。时间复杂度 $O(n)$ 。

第一种方法不必多述，而对于第二种方法：我们用 $dp_{k,x},k \in \{0,1\},x \in n$ 来记录该点所能到达其子树的最远距离和次远距离。

例题

P3047 [USACO12FEB]Nearby Cows G

对于一个点 $x$ ，与它相距不超过 $k$ 的点有两种情况：

  • 在 $x$ 的儿子之中。
  • 在 $x$ 之上（或其父节点的另一棵子树）

那么我们进行两次遍历，第一次查找每一个点向下查找能找到的点权值，记为 dp[0][x][k] ，第二次查找父节点满足条件的点权值，将两次计算相加即可。需要进行容斥。

AC Code 
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int MAXK=21;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N,K,Val[MAXN];
struct Tree
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
int dp[2][MAXN][MAXK];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(Tree){Head[u],v};Head[u]=Total;
    Edge[++Total]=(Tree){Head[v],u};Head[v]=Total;
}
void dfs(int x,int last)
{
    for(int i=0;i<=K;++i) dp[0][x][i]=Val[x];
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfs(v,x);
        for(int i=1;i<=K;++i) dp[0][x][i]+=dp[0][v][i-1];
    }
}
void dfsSec(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dp[1][v][1]+=dp[0][x][0];
        for(int i=2;i<=K;++i) dp[1][v][i]+=dp[1][x][i-1]-dp[0][v][i-2];
        dfsSec(v,x);
    }
}
int main()
{
    // freopen("tredp.in","r",stdin);
    // freopen("tredp.out","w",stdout);
    read(N),read(K);
    for(re int i=1;i<N;++i)
    {
        int u,v;
        read(u),read(v);
        addEdge(u,v);
    }
    for(re int i=1;i<=N;++i) read(Val[i]);
    dfs(1,-1);
    for(int i=1;i<=N;++i)
        for(int j=0;j<=K;++j)
            dp[1][i][j]=dp[0][i][j];
    dfsSec(1,-1);
    for(int i=1;i<=N;++i) printf("%d\n",dp[1][i][K]);
    return 0;
}
/*
6 2 
5 1 
3 6 
2 4 
2 1 
3 2 
1 
2 
3 
4 
5 
6 
*/

P7103 「C.E.L.U-01」族谱树

这道题其实并不是一道纯粹树型 $dp$ 。直接用 $Tarjan$ 求所有深度的 $lca$ 即可。复杂度 $O(n+q)$ 。据说 $O(n \log n)$ 会被卡。不清楚。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=5e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N,M,K[MAXN],Q;
struct Tree
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
int f[MAXN],dep[MAXN];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(Tree){Head[u],v};Head[u]=Total;
}
int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
void dpTree(int x,int last)
{
    dep[x]=dep[last]+1;
    for(int e=Head[x];e;e=Edge[e].next) dpTree(Edge[e].to,x),f[Edge[e].to]=x;
    K[dep[x]]=K[dep[x]]?find(K[dep[x]]):x;
}
int main()
{
    // freopen("tredp.in","r",stdin);
    // freopen("tredp.out","w",stdout);
    read(N),read(M);
    for(int i=1,fa;i<=N;++i)
    {
        read(fa);f[i]=i;
        addEdge(fa,i);
    }
    dpTree(1,-1);
    while(M--)
    {
        read(Q);
        printf("%d\n",K[Q]);
    }
    return 0;
}
/*
8 3
0 1 1 2 2 3 4 5
2
1
4
*/

Loj#10155. 「一本通 5.2 例 3」数字转换

这题我还比较喜欢。不看标签我是绝对不会想到用树型 $dp$ 来解的。我们记数 $i$ 的约数和为 $f(i)$ 。而当 $f(i) \leq i$ 时，可以互相转换。如果将每一个数都看作一个节点，则我们连一条边 $c(i,f(i))$ 。然后对于这一个无向图。求出其直径即可。而对于线性求约数和。读者可以自行思考如何实现复杂度 $O(n \log n)$，或者看代码。

AC Code 
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
74
75
76
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int Limit,f[MAXN],dp[3][MAXN],ans;
inline void init()
{
    for(int i=1;i<MAXN;++i) f[i]=1;
    for(int i=2;i<MAXN;++i)
        for(int j=2;i*j<MAXN;++j)
            f[i*j]+=i;
}
struct Tree
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(Tree){Head[u],v};Head[u]=Total;
    Edge[++Total]=(Tree){Head[v],u};Head[v]=Total;
}
void dpTree(int x,int last)
{
    for(int e=Head[x];e;e=Edge[e].next)
    {
        int v=Edge[e].to;
        if(v==last||v==x) continue;
        dpTree(v,x);
        if(dp[1][x]<dp[1][v]+1)
        {
            dp[2][x]=dp[1][x];
            dp[1][x]=dp[1][v]+1;
        }
        else if(dp[2][x]<dp[1][v]+1) dp[2][x]=dp[1][v]+1;
        ans=max(ans,dp[1][x]+dp[2][x]);
    }
}
int main()
{
    // freopen("tree-d.in","r",stdin);
    // freopen("tree-d.out","w",stdout);
    init();
    read(Limit);
    for(int i=1;i<=Limit;++i) if(i>=f[i]) addEdge(i,f[i]);
    // for(int i=1;i<=Limit;++i) cout<<i<<" "<<f[i]<<endl;
    dpTree(1,-1);
    printf("%d",ans);
    return 0;
}
/*
7
79
*/

二次扫描与换根法

因为考到了所以又回来重新学习。

这个思路用于求解一棵无根树，且不定根时的最值答案。主要就是首先随机一个点为根，跑一遍 $\text{dp}$ ，再利用求得的解再一次动态规划，第二次的动态规划称为换根。

例题

P3478

求得一个根使 $\displaystyle\sum dep_i$ 最大。

不难看出，遍历所得答案的时间复杂度是 $\mathcal O(n^2)$ 。而换根 $\text{dp}$ 可以优化到 $\mathcal O(n)$ 。

设当前根节点为 $u$ ，我们接下来会将根切换到 $u$ 的子结点 $v$ 上。那么，对于这次换根的影响，我们会发现，所有 $v$ 子树上的结点（包括 $v$ ），深度都会减一，而其他结点的深度加一。

那么，就可以得到一个递推式，设以 $u$ 为根结点的深度和为 $f[u]$ ，则有：

$f[v]=f[u]-size[v]+(size[1]-size[v])$

第一次扫描时设的根结点是 $1$ 。

然后最后扫描一遍并记录最大答案即可。

AC Code 
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
74
75
#include<bits/stdc++.h>
const int MAXN=1e6+10;
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int N;
struct Tre
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
ll dp[MAXN],Siz[MAXN],Dep[MAXN];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(Tre){Head[u],v};Head[u]=Total;
    Edge[++Total]=(Tre){Head[v],u};Head[v]=Total;
}
void dfsPre(int x,int last)
{
    Siz[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsPre(v,x);
        Siz[x]+=Siz[v];
    }
}
void dfsCalc(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dp[v]=dp[x]+Siz[1]-Siz[v]*2;
        dfsCalc(v,x);
    }
}
ll Ans=-0x3f3f3f3f,idx;
int main()
{
    read(N);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
    }
    dfsPre(1,0);dfsCalc(1,0);
    for(int i=1;i<=N;++i)
        if(dp[i]>Ans)
        {
            Ans=dp[i];
            idx=i;
        }
    printf("%lld",idx);
}
/*
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
*/

P2986

比较基础，甚至 $\text{H}_2\text{O}$ 了一道蓝题。

转移方程：$dp[v]=dp[x]+(Siz[1]-2Siz[v])\times val[e]$

其中 $e$ 为边 $(u,v)$ ，$Siz[u]$ 表示以 $u$ 为根结点的子树中的牛的个数。

AC Code 
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
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define gh() getchar()
const int MAXN=1e5+10;
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int N,C[MAXN];
struct Tre
{
    int next,to,val;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Tre){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Tre){Head[v],u,w};Head[v]=Total;
}
ll dp[MAXN],Siz[MAXN],Dist[MAXN];
void dfsPre(int x,int last)
{
    Siz[x]=C[x];
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        Dist[v]=Dist[x]+Edge[e].val;
        dfsPre(v,x);
        Siz[x]+=Siz[v];
    }
}
void dfsCalc(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dp[v]=dp[x]+(Siz[1]-2*Siz[v])*Edge[e].val;
        dfsCalc(v,x);
    }
}
ll ans=1e18;
int main()
{
    read(N);
    for(int i=1;i<=N;++i) read(C[i]);
    for(int i=2,u,v;i<=N;++i)
    {
        ll w;
        read(u,v,w);addEdge(u,v,w);
    }
    Dist[1]=0;
    dfsPre(1,0);
    for(int i=1;i<=N;++i) dp[1]+=Dist[i]*C[i];
    dfsCalc(1,0);
    for(int i=1;i<=N;++i) ans=std::min(ans,dp[i]);
    write(ans);
}
/*
5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3 
*/
相关文章