HDU 2196 Computer（树形dp）

$HDU2196Computer（树形dp）$

题目链接：Problem - 2196 (hdu.edu.cn)

题意

给出一个n个节点的无根树，求每个节点所能到达的最远距离。

思路

• 本题解思路为树形dp思路。
• 注意题目的输入要求。
• 题目为多实例！

跟据二叉树的定义，每个节点至多有一个父节点（只有根节点没有），我们会发现每个节点能够到达的最远距离只有下图两种情况。

那么我们可以先通过一次dfs，从叶节点向上返回；记录每个节点的子节点中的最大路径长度和次大路径长度，因为会出现图片中①的情况。

然后再通过一次dfs，从根节点向下遍历；找出每个节点的最大反向路径长度，对应的是图片中的②情况。

对于最大路径长度、次大路径长度、最大反向路径长度，我们可以用$dp[i][j],j\in (0,1,2)$来记录每个节点的状态。

在第二次dfs的过程中，我们可以对每个节点的子节点进行状态转移，状态转移方程为：
{ d p [ 2 ] [ s o n ] = m a x ( d p [ 2 ] [ f a t h e r ] , d p [ 1 ] [ f a t h e r ] + w e i g h t )     s o n 为 f a t h e r 子节点中的最大路径 d p [ 2 ] [ s o n ] = m a x ( d p [ 2 ] [ f a t h e r ] , d p [ 0 ] [ f a t h e r ] + w e i g h t )     s o n 不为 f a t h e r 子节点中的最大路径

$$\begin{cases} & \text dp[2][son] = max(dp[2][father], dp[1][father]+weight) ~~~ son为father子节点中的最大路径\\ & \text dp[2][son] = max(dp[2][father], dp[0][father]+weight) ~~~ son不为father子节点中的最大路径 \end{cases}$$ {​dp[2][son]=max(dp[2][father],dp[1][father]+weight)   son为father子节点中的最大路径dp[2][son]=max(dp[2][father],dp[0][father]+weight)   son不为father子节点中的最大路径​
其中$0,1,2$分别对应的是最大路径长度、次大路径长度、最大反向路径长度。

最后每个节点能够到达的最远距离即为：$max(dp[0][i],dp[2][i])$。

标程

const int N = 10000 + 10; 

struct Edge {int to, weight;};  // 边
vector<vector<Edge>> tree;      //用于存储树的结构
int n, dp[3][N], id[N];

void dfs1(int x, int y) {
    for(auto i : tree[x]) {//正向最大距离
        if(i.to == y) continue;
        dfs1(i.to, x);
        if(dp[0][x] < dp[0][i.to] + i.weight) {
            dp[0][x] = dp[0][i.to] + i.weight;
            id[x] = i.to;
        }
    }
    for(auto i : tree[x]) {//正向次大距离
        if(i.to == y) continue;
        if(id[x] == i.to) continue;
        dp[1][x] = max(dp[1][x], dp[0][i.to] + i.weight);
    }
}

void dfs2(int x, int y) {
    for(auto i : tree[x]) {//反向最大距离
        if(i.to == y) continue;
        if(i.to == id[x])
            dp[2][i.to] = max(dp[2][x], dp[1][x]) + i.weight;
        else
            dp[2][i.to] = max(dp[2][x], dp[0][x]) + i.weight;
        dfs2(i.to, x);
    }
}

void init() {
    tree.clear(); tree.resize(n + 1);
    memset(dp, 0, sizeof dp);
    memset(id, 0, sizeof id);
}

void Solved() { 
    while(cin >> n) {
        init();
        for(int i = 2; i <= n; i ++ ) {
            int x, y; cin >> x >> y;
            tree[x].push_back({i, y});
            tree[i].push_back({x, y});
        }
        dfs1(1, -1); dfs2(1, -1);

        for(int i = 1; i <= n; i ++ ) {
            cout << max(dp[0][i], dp[2][i]) << endl;
        }
    }
}
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