题目描述

难度分:$1600$

输入$T(\leq 5000)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$。

每组数据输入$n(2 \leq n \leq 3 \times 10^5)$和一棵$n$个节点的二叉树的$n-1$条双向边。节点编号从$1$开始。

二叉树的根节点是$1$。一开始，根节点被感染。然后执行如下过程$n$次：

• 首先，选择一个未被感染也未被删除的点，将其删除（相连的边也删除）；或者什么也不做。
• 然后，任何与被感染节点相邻的节点，都被感染。

输出最多可以让多少个节点不被感染也不被删除。

输入样例

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

输出样例

0
2
2
10

算法

树形DP

这个感染过程还是挺形象的，我们的目的其实就是想要未感染的节点最多。

状态定义

$dp[u]$表示以$u$为根的子树中能保留的最多不会被感染的节点数目。在这个定义下，答案就应该是$dp[1]$。

状态转移

对于某个子树的根节点$u$：

1. 假设它有两个孩子$lch$和$rch$，此时只能阻断$u$向一个子树感染，如果阻断$lch$，就有状态转移$dp[u]=cnt[lch]-1+dp[rch]$，如果阻断$rch$，则有状态转移$dp[u]=cnt[rch]-1+dp[lch]$，两者取较大值转移。
2. 只有一个孩子$ch$的话，则有$dp[u]=cnt[ch]-1$。
3. 如果没有孩子，则有$dp[u]=0$。

其中$cnt[u]$表示以$u$为根的子树中有多少个节点，很典，也可以用树形DP求出来。整个算法只需要DFS两遍做两次树形DP。

复杂度分析

时间复杂度

树形DP两遍，相当于DFS遍历整棵树两遍，时间复杂度为遍历二叉树的时间复杂度，即$O(n)$。

空间复杂度

树的邻接表空间消耗为$O(n+m)$，其中$m$是边数，$n$是顶点数，由于是树，所以顶点数和边数是同一级别，空间复杂度为$O(n)$。记录子树节点树的$cnt$数组空间消耗也是$O(n)$。在DFS的过程中递归深度在最差情况下为$O(n)$，即整棵树退化成链的情况。因此，整个算法的额外空间复杂度就是$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 300010;
int T, n, cnt[N];
vector<int> graph[N];

void dfs1(int u, int fa) {
    cnt[u] = 1;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        cnt[u] += cnt[v];
    }
}

int dfs2(int u, int fa) {
    vector<int> child;
    for(int v: graph[u]) {
        if(v != fa) {
            child.push_back(v);
        }
    }
    if(child.empty()) return 0;
    if(child.size() == 1) return cnt[child[0]] - 1;
    int lch = child[0], rch = child[1];
    return max(cnt[lch] - 1 + dfs2(rch, u), cnt[rch] - 1 + dfs2(lch, u));
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            cnt[i] = 0;
            graph[i].clear();
        }
        for(int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs1(1, 0);
        printf("%d\n", dfs2(1, 0));
    }
    return 0;
}