[动态规划] 树形DP

树形DP

树的最长路径

https://www.acwing.com/problem/content/1074/

思路

题意

在这里插入图片描述

由于是无向树，所以可以随意选择某个顶点作为根

以子树的根来作为划分依据，最长路径等于子树的最大路径长度和次最大路径长度之和

C++ 代码

#include 
#include 
#include 

using namespace std;

const int N = 10010, M = 2 * N;

int n;
int h[N], e[M], w[M], ne[M], idx;
int ans;

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

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

int dfs(int u, int fa) {
    int dist = 0;
    int d1 = 0, d2 = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int d = dfs(j, u) + w[i];
        dist = max(d, dist);
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    cout << dist << endl;
    ans = max(ans, d1+d2);
    return dist;
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 0; i < n-1; i ++) {
        int a, b, c;
        a = read();
        b = read();
        c = read();
        add(a, b, c), add(b, a, c);
    }
    dfs(5, -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

树的中心

原题链接

https://www.acwing.com/problem/content/1075/

思路

题意

求某一点到树中其他结点的最远距离的最小值

对树的顶点按照上方和下方划分，对于某一个顶点而言，最远距离等于下方的最远距离和上方的最远距离取最大值

树的下方可按照上题方法来做，上方其实也是类似，做两遍 dfs

C++ 代码

#include 
#include 
#include 

using namespace std;

const int N = 10010, M = 2 * N, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], up[N], p1[N];
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

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

int dfs_down(int u, int fa) {
    d1[u] = d2[u] = -INF;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int d = dfs_down(j, u) + w[i];
        if (d >= d1[u]) {
            d2[u] = d1[u], d1[u] = d;
            p1[u] = j;
        }
        else if (d > d2[u]) d2[u] = d;
    }
    if (d1[u] == -INF) d1[u] = d2[u] = 0;
    if (d2[u] == -INF) d2[u] = 0;
    return d1[u];
}

void dfs_up(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        if (j == p1[u]) {
            up[j] = max(d2[u], up[u]) + w[i];
        } else {
            up[j] = max(d1[u], up[u]) + w[i];
        }
        dfs_up(j, u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 0; i < n-1; i ++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    int res = INF;
    for (int i = 1; i <= n; i ++) {
        res = min(res, max(d1[i], up[i]));
    }
    printf("%d\n", 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
70
71
72
73
74

树的中心

原题链接

https://www.acwing.com/problem/content/1075/

思路

题意

求某一点到树中其他结点的最远距离的最小值

对树的顶点按照上方和下方划分，对于某一个顶点而言，最远距离等于下方的最远距离和上方的最远距离取最大值

树的下方可按照上题方法来做，上方其实也是类似，做两遍 dfs

C++ 代码

#include 
#include 
#include 

using namespace std;

const int N = 10010, M = 2 * N, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], up[N], p1[N];
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

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

int dfs_down(int u, int fa) {
    d1[u] = d2[u] = -INF;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int d = dfs_down(j, u) + w[i];
        if (d >= d1[u]) {
            d2[u] = d1[u], d1[u] = d;
            p1[u] = j;
        }
        else if (d > d2[u]) d2[u] = d;
    }
    if (d1[u] == -INF) d1[u] = d2[u] = 0;
    if (d2[u] == -INF) d2[u] = 0;
    return d1[u];
}

void dfs_up(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        if (j == p1[u]) {
            up[j] = max(d2[u], up[u]) + w[i];
        } else {
            up[j] = max(d1[u], up[u]) + w[i];
        }
        dfs_up(j, u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 0; i < n-1; i ++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    int res = INF;
    for (int i = 1; i <= n; i ++) {
        res = min(res, max(d1[i], up[i]));
    }
    printf("%d\n", 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
70
71
72
73
74

数字转换

原题链接

https://www.acwing.com/problem/content/1077/

思路

题意

通过分析可得，每个数的 $x$ 的约数之和 $y$ 是固定的，也就是每个数只有唯一一个对应的约数之和，因此可以从 $y$ 向 $x$ 连一条有向边，利用这个性质可以按照这样的方式建树，无向边就转化为了有向边(当然无向边也是可以的，只不过需要多开两倍的数组空间)

本质上就是求树中的直径，权值为1

C++ 代码

#include 
#include 
#include 

using namespace std;

const int N = 50010, M = N;

int n;
int sum[N];
int h[N], e[M], ne[M], idx;
bool st[N];
int res;
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

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

int dfs(int u) {
    int d1 = 0, d2 = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        int d = dfs(j) + 1;
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    res = max(res, d1 + d2);
    return d1;
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 1; i <= n; i ++)
        for (int j = 2; j <= n / i; j ++)
            sum[i * j] += i;
    for (int i = 2; i <= n; i ++)
        if (i > sum[i])
            add(sum[i], i), st[i] = true;
    
    for (int i = 1; i <= n; i ++)
        if (!st[i]) dfs(i);
    printf("%d\n", 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

代码解析

在求约数时，利用试除法时间复杂度过高，为 $O(N\sqrt{N})$ . 可以反过来考虑，对于每个数 $d$ ， $1\sim N$ 中以 $d$ 为约数的数就是 $d$ 的倍数， $\lfloor N/d \rfloor*d$ ，时间复杂度为 $O (Nl o g N)$
另外记录根结点，然后 dfs 时从根结点开始，因为生成的并不是完整的一棵树，而是森林，其中以 $1$ 为根结点生成的树最大，而我们的答案就在其中。实测只 dfs(1) ，也能 AC ，但并没有严谨的证明对于所有的数据都适用，最好还是遍历所有的树

相关阅读:
在Cygwin环境下构建和使用EmberZNet PRO Zigbee Host应用程序
有关CSS的芝士
如何部署lvs负载均衡集群 DR模式
【Linux篇】之samba服务器配置
如何删除重复文件？简单操作法方法盘点！
【OpenCV-Python】教程：3-10 直方图（2）直方图均衡
Python多方法高效匹配、关联操作两个列表
基于Java+SpringBoot+Mybatis+Vue+ElementUi的幼儿园管理系统
将本地jar打包到本地maven仓库或maven私服仓库中
如何使用autotools制作Makefile

原文地址：https://blog.csdn.net/Joker15517/article/details/125902506