一键难忘520

这个屌丝很懒，什么也没留下！

热门标签

【蓝桥杯】树形DP专题

作者：一键难忘520 | 2024-08-18 07:20:52

踩

树形dp专题

文章目录

树形DP

树形DP

树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。整体的思路大致就是用树形的结构存储数据。

树形dp每次以子树为单位进行计算。

树形DP的关键和实现方法是dfs。
$先找到树根，从树根开始运用 d f s 递归，跟 d f s 一样先初始化，然后递归到叶子节点上为止，把最底层的 f [i] [j] 更新完毕，再回来往上走，自底向上地根据题意更新上层的 f 数组，最后输出答案即可。$
在这里插入图片描述

1.没有上司的舞会

【题目链接】285. 没有上司的舞会 - AcWing题库

Ural 大学有 N 名职员，编号为 1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 HiHi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 N。

接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。

接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000,
−128≤Hi≤127

输入样例：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输出样例：
5
1

思路：

树形dp

状态表示
f[u][0]：所有以u为根的子树中选择，并且不选u这个点的方案

f[u][1]：所有以u为根的子树中选择，并且选u这个点的方案

属性：Max

状态计算
当前u结点不选，子结点可选可不选

f[u][0]=∑max(f[si,0],f[si,1])
当前u结点选，子结点一定不能选

f[u][1]=∑(f[si,0])
时间复杂度： O(n)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 6010;

int dp[N][2];
int h[N], e[N], ne[N], idx;
int happy[N];
bool vis[N];
int n;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    dp[u][1] = happy[u];// 如果选择u这个点的话 需要先加上这个点的高兴度！
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        
        dp[u][0] += max(dp[j][0], dp[j][1]);//不选u这个根节点
        dp[u][1] += dp[j][0];// 选择u这个根节点
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);// 开心值（点权）
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        vis[a] = true; // 表示它有父节点
    }
    
    //寻找根节点
    int root = 1;
    while(vis[root]) root ++;
    dfs(root);
    
    printf("%d\n", max(dp[root][0], dp[root][1]));// 选择根节点的最大值和不选择根节点的最大值
    
    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

2.生命之树

【题目链接】1220. 生命之树 - AcWing题库

在X森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。

上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得 S 中的点所对应的整数的和尽量大。

这个最大的和就是上帝给生命之树的评分。

经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。

但是由于 atm 不擅长计算，他不知道怎样有效的求评分。

他需要你为他写一个程序来计算一棵树的分数。

输入格式
第一行一个整数 n 表示这棵树有 n 个节点。

第二行 n 个整数，依次表示每个节点的评分。

接下来 n−1 行，每行 2 个整数 u,v，表示存在一条 u 到 v 的边。

由于这是一棵树，所以是不存在环的。

树的节点编号从 1 到 n。

输出格式
输出一行一个数，表示上帝给这棵树的分数。

数据范围
1≤n≤105,
每个节点的评分的绝对值均不超过 106。

输入样例：
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
1
2
3
4
5
6
输出样例：
8
1

算法分析：

树形dp

状态表示
f[u]:在以u为根的子树中包含u的所有连通块的权值和的最大值
状态计算
假设s1，s2,…sk 是u的孩子，各个子树之间是相互独立的，要使得答案最大，那么它的子树就要最大

f[u]= w[u] + ∑max(f[s1,0], f[s2,0] + ....f[sk,0])
从根结点开始深度优先遍历每个子结点

注：

树不一定是二叉树
因为是无向边，搜完之后必定会往回搜索，因此我们要尽量避免往回搜（不然空间太大了），因此就将记录好每一个节点是从哪里来的，即记录父节点。

时间复杂度 O(n)，取决于树的边的个数！

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
LL w[N];
LL dp[N];// 以u为节点的包含u的子树（连通块）的最大值
int n;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
// 由于是无向边，因此要尽量避免往回搜索
void dfs(int u, int father)
{
    dp[u] = w[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j != father)// 如果不是往回搜，则深搜
        {
            dfs(j, u);
            dp[u] += max(0ll, dp[j]);
        }
       
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];// 点权
    
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);//且序列中相邻两个点间有一条边相连 --- 无向树
    }
    
    dfs(1, -1);// 因为是无向图，因此可以从任意节点开始
    LL res = -1e18;
    for (int i = 1; i <= n; i ++ ) res = max(res, dp[i]);
    
    cout << res;
    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

3.左孩子右兄弟

可能有以下 3 种 (这里只列出 3 种，并不是全部) 不同的 “左孩子右兄弟” 表示：

其中最后一种高度最高，为 4。

输入格式

输入的第一行包含一个整数 NN。

以下 N−1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。

输出格式

输出一个整数表示答案。

数据范围

对于 30% 的评测用例，1≤N≤20；
对于所有评测用例，1≤N≤105。

输入样例：
5
1
1
1
2
1
2
3
4
5
输出样例：
4
1

【代码实现】

求树的最大深度：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;

int num[N];
int f[N]; 
//f[u]：表示以u为根节点的，通过 “左孩子右兄弟” 表示法转化成二叉树后的所有方案的集合；
// 属性：max
//f[u] = max(f[u], f[j] + num[u])
// 最大高度为：u的所有孩子节点 + 某个孩子子树的最大值
int n;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        f[u] = max(f[u], f[j] + num[u]);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 2; i <= n; i ++ )
    {
        int fa;
        cin >> fa;
        num[fa] ++;// 以fa为根节点的孩子数
        add(fa, i);
    }
    dfs(1, -1);
    cout << f[1];
    
    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

4.树的重心

在这里插入图片描述

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2 * N;

int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx, idx ++;
}

//返回以u为根节点的子树中节点的个数，包括u节点
int dfs(int u)
{
    st[u] = true;// 标记一下，已经搜索过
    
    //size是表示将u点去除后，剩下的子树中数量的最大值；
    //sum表示以u为根的子树的点的多少，初值为1，因为已经有了u这个点
    int size = 0, sum = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];//拿到出边的对应的节点编号
        if(!st[j])
        {
            int s = dfs(j); // 当前子树的大小（//s是以j为根节点的子树中点的数量）
            size = max(size, s);// 取子树种节点数较大者（连通块最大值）
            sum += s;
        }
    }
    //n-sum表示的是减掉u为根的子树，整个树剩下的点的数量
    size = max(size, n - sum);
    ans = min(ans, res);
    
    return sum;
}

int main()
{
    
    cin >> n;
    //初始化链表
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);//无向图
    }
    //从第一个节点开始搜索
    dfs(1);
    printf("%d\n", ans);
    
    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

5.大臣的旅费

【题目链接】大臣的旅费 - 蓝桥云课 (lanqiao.cn)
在这里插入图片描述

d表示走的千米数，s表示花费

1：11

2：11 + 12

3：11 + 12 + 13

…

得出下面公式

在这里插入图片描述

要使得s最大，那么d就要尽可能的大，求出距离最远的两个节点之间的距离，即求树的直径（树可能有多条直径，但此题我们要求的是权值和最大的那条直径）

1.两次dfs求树的直径

求树的直径算法步骤：

以一个结点为起点，找出与这个结点距离最远的结点，记为结点 k1
以结点 k1为起点，找出与其距离最远的结点，记为结点 k2
则 k1和 k2之间的距离即为树的直径

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n;
int h[N], e[2 * N], ne[2 * N], w[2 * N], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dist[N];

void dfs(int u, int father, int distance)
{
    dist[u] = distance;
    
    // 遍历节点u的所有出边对应的点
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j != father)
            dfs(j, u, distance + w[i]);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ )// n个点有n-1条边
    {
        int a, b, c;
        cin >> a >> b >> c;
        //存储无向边
        add(a, b, c);
        add(b, a, c);
    }
    
    // 第一遍dfs
    // 找到任意点x找到距离最远的点y
    dfs(1, -1, 0);// 参数1：(当前节点编号)节点1开始;参数2：从哪个节点来（防止回搜索）参数3：当前节点到选点（1号节点）的距离
    // 找出最远距离
    int u = 1;
    for(int i = 1; i <= n; i ++)
        if(dist[i] > dist[u])
            u = i;
    // 第二遍dfs
    // 找到离y最远的点的距离
    dfs(u, -1, 0);
    for(int i = 1; i <= n; i ++)
        if(dist[i] > dist[u])
            u = i;
            
    // 树的直径        
    int s = dist[u];  
    
    LL res = s * 10 + s * (s + 1ll) / 2;
    cout << res;
    
    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

2.树形dp

思路：最远距离 + 次远距离即为树的直径
【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
LL d1[N], d2[N];// 以u为根节点的往下走的最大值和次大值
LL maxd;// 树的直径
int n;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}


// 无向树，避免往回走
void dfs_d(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j != father)
        {
            dfs_d(j, u);// 递归完后，儿子的最大值、次大值都有了
            LL distance = d1[j] + w[i];// 最大
            if(distance > d1[u])// 当前的最大值比原来的最大值还大，更新
            {
                d2[u] = d1[u], d1[u] = distance;
            }
            // 不能更新最大值，退而求其次，更新次大值
            else if(distance > d2[u]) d2[u] = distance;            
        }

    }
    maxd = max(maxd, d1[u] + d2[u]);// 更新求树的直径
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dfs_d(1, -1);// 第一遍dfs得到树的直径，该节点的最长长度和次大长度
    LL s = maxd;
    LL res = s * 10 + s * (s + 1ll) / 2;
    cout << res;
   
    
    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

6.旅游规划

1、先通过树形dp求出每个点往下走的最大长度和次大长度，并且更新整棵树的最大路径maxd，d1[i] + d2[i] == maxd。

2、如何判断点在直径上？ (往下走最大值（已求） + 往上走最大值 == 直径，即在直径上)
往上走怎么求？ (取决于u这个点往上走或往下走的最大值(特判往下走不能走回))

在这里插入图片描述

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 2e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int d1[N], d2[N];// 以u为根节点的往下走的最大值和次大值
int up[N];
int p1[N];
int maxd;// 树的直径
int n;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 无向树，避免往回走
void dfs_d(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j != father)
        {
            dfs_d(j, u);// 递归完后，儿子的最大值、次大值都有了
            int distance = d1[j] + 1;// 最大
            if(distance > d1[u])// 当前的最大值比原来的最大值还大，更新
            {
                d2[u] = d1[u], d1[u] = distance;
                p1[u] = j;//记录： u节点往下走是j
            }
            // 不能更新最大值，退而求其次，更新次大值
            else if(distance > d2[u]) d2[u] = distance;            
        }

    }
    maxd = max(maxd, d1[u] + d2[u]);// 更新求树的直径
}


void dfs_u(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j != father)
        {
            up[j] = up[u] + 1;// up数组和父节点有关（往上的情况）
            // 往下的两种情况  //说明从j向下走是从u向下走最长路径
            if(p1[u] == j) up[j] = max(up[j], d2[u] + 1);// 用第二长的路径更新up数组
            else up[j] = max(up[j], d1[u] + 1);// 说明从j向下走不是从u向下走的最长路径，用最长的路径更新up数组
            dfs_u(j, u);            
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs_d(0, -1);// 第一遍dfs得到树的直径，该节点的最长长度和次大长度
    dfs_u(0, -1);// 搜索往上走的最大值 最终由往上走的最大值和往下走最大值之和，判断该点是否在树的直径上
    
    // 枚举每一个点，康康是否可以在直径上
    for(int i = 0; i < n; i ++)
    {
        int d[3] = {d1[i], d2[i], up[i]};
        sort(d, d + 3);
        if(d[1] + d[2] == maxd) printf("%d\n", 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
74
75
76
77
78
79
80
81
82
83
84

参考文献：

acwing题库

蓝桥杯题库

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】