Infected Tree(树形dp)

原题链接

题目描述

Misha发现了一棵二叉树，它的顶点编号从到。二叉树是一种包含顶点和边的无环连通双向图。每个顶点最多有一个度，而根顶点是有个数的顶点，它最多有一个度。

不幸的是，树根被感染了。

以下过程发生的次数:

Misha要么选择一个未被感染(也没有被删除)的顶点，并删除它，所有的边都有一个端点在这个顶点，或者什么都不做。

然后，感染扩散到由一条边连接到已感染顶点的每个顶点(所有已感染顶点仍然是感染的)。

由于Misha没有太多时间思考，请告诉他他可以从感染中拯救的最大顶点数是多少(注意删除的顶点不计入保存)

输入样例

4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15

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

输出样例

0
2
2
10
1
2
3
4

---

算法

(树形dp)

本题可以通过维护一个 dp 数组可以快速统计 每一个点作为根节点保留左子树或者保留右子树的最大保留人数 ，从而最后通过 dfs 过程中更新迭代，生成最后需要的答案。

值得注意的是题目的删除点及其子树的顺序是从根到枝叶，但在树形 dp 的统计过程中应该从枝叶到根进行 dp 数组统计，因为最后保留的都是每一层的枝叶，一般的树形 dp 业主要是以这样的方式统计

状态方程：
dp[u][0] = sum[l[u]] - 1 + max(dp[r[u]][1],dp[r[u]][0]);//保留左子树
dp[u][1] = sum[r[u]] - 1 + max(dp[l[u]][1],dp[l[u]][0]);//保留右子树

C++ 代码

时间复杂度 $O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
vector<int> g[N];
int dp[N][2];//每一个点作为根节点保留左子树或者保留右子树的最大保留人数
int sum[N],l[N],r[N];//以u为根节点能够保留的总人数，u节点的左节点与右节点

void pre_dfs(int u,int fa)//预处理
{
    sum[u] = 1;
    for (int i = 0;i < g[u].size();i ++ ) {
        int j = g[u][i];
        if (j == fa) continue;
        //经典代码，利用dfs的规律分别指定左右节点
        if (l[u] == 0) l[u] = j;
        else r[u] = j;

        pre_dfs(j,u);
        sum[u] += sum[j]; 
    }
}
void dfs(int u,int fa) 
{
    dp[u][1] = dp[u][0] = 0;//初始化
    for(int i = 0;i < g[u].size();i ++ ){
        int j = g[u][i];
        if (j == fa) continue;
        dfs(j,u);
        //最后进行dp统计
        dp[u][0] = sum[l[u]] - 1 + max(dp[r[u]][1],dp[r[u]][0]);//save left subtree
        dp[u][1] = sum[r[u]] - 1 + max(dp[l[u]][1],dp[l[u]][0]);//save right subtree
    }
}
int main()
{
    int t;
    cin >> t;
    while (t -- ) {
        int n;
        cin >> n;
        int m = n - 1;
        for (int i = 1;i <= n;i ++ ) {
            sum[i] = l[i] = r[i] = 0;
            g[i].clear();
        }
        for (int i = 0;i < m;i ++ ) {
            int u,v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        pre_dfs(1,1);
        dfs(1,1);
        cout << max(dp[1][0],dp[1][1]) << '\n';
    }
    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