D. 小红的奇数奶油球

题目描述

小红制作了一个精美的创意甜品，该甜品由 n 个奶油球（编号 1 到 n）组成。这些奶油球之间通过奶油拉花连接，恰好构成一棵树的结构。

小红认为，一个奶油球是 “完美的”，当且仅当满足以下条件：

如果将这个奶油球以及与之相连的所有拉花拆除，剩下的每一个连通部分（即剩下的奶油球簇，或者严谨的说，极大连通分量）所包含的奶油球个数都必须是奇数。
特别的，如果整棵树只有 1 个节点，那么认为该节点是 “完美的”。

小红想知道，在这个甜品中共有多少个 “完美的” 奶油球？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ （ $1≤T≤10^4$ ）代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $n$ （ $1≤n≤2×10^5$ ），表示奶油球的数量。

此后 $n−1$ 行，第 i 行输入两个整数 $u_i$ 和 $v_i$ （ $1≤ui,vi≤n$ ），表示奶油球 $u_i$ 和 $v_i$ 之间有一条奶油拉花相连。保证所有的拉花连接构成一棵树。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行输出一个整数，表示 “完美的” 奶油球的总数。

示例 1

输入

输出

1
1
4

说明

对于第一组测试数据：

移除 1：剩 {2,3} 大小 2，不满足；
移除 2：剩 {1}、{3} 大小 1、1，满足；
移除 3：剩 {1,2} 大小 2，不满足；
因此，只有编号为 2 的奶油球是符合条件的 “完美的” 奶油球，答案为 1。

对于第二组测试数据：

移除 1：剩 {2}、{3,4,5} 大小 1、3，满足；
移除 2：剩 {1,3,4,5} 大小 4，不满足；
移除 3：剩 {4}、{5}、{1,2} 大小 1、1、2，不满足；
移除 4：剩 {1,2,3,5} 大小 4，不满足；
移除 5：剩 {1,2,3,4} 大小 4，不满足；
因此，只有编号为 1 的奶油球是符合条件的 “完美的” 奶油球，答案为 1。

题解

思路

题目要求我们找到完美节点。一个节点是完美的，意味着移除它之后，所有剩下的极大连通分量的大小size都必须是奇数。

当我们移除树上的一个节点 u 时，剩下的连通块分为两类：

子树大小：u 的每一个子节点 v 及其下节点形成一个连通块。这个连通块的大小就是以 v 为根的子树大小，记为 size[v]。
父节点之上大小：u 的子树之上的所有节点构成一个连通块。这个连通块的大小为 n - size[u]（总节点数减去 u 的子树大小）。

我们需要检查u的两个部分：

子节点的子树大小是否为奇数。
父节点方向的连通块大小是否为奇数。

方法

存储的数据结构：使用邻接表存储，存储每一个节点。
深度优先搜索：
- 初始化记录当前节点child_size为1，自己也存进去。
- 我们在 DFS 的过程中，利用递归+回溯的策略求出每个节点的子树大小 child_size。
- 状态转移方程：child_size[curr] = sum(child_size[child]) + 1。在这题，我们可以写child_size[curr] += child_size[child]不断累加。
判断逻辑：
- 在DFS处理完当前节点的所有子节点后，我们就可以直到这个节点所有的 child_size。
- 遍历当前节点的所有子节点，检查 child_size[child] 是否为偶数。如果是，就不是perfect的。
- 检查 n - child_size[curr]，如果大于 0 （等于0不就是自己是根了嘛，这时候不需要看这个）且为偶数，就不是perfect的。
- 如果结束了还是perfect的，记录 result++。

复杂度

时间复杂度： O(N)

空间复杂度： O(N)

代码实现

C++：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int result;

//计算子树大小并判断节点是否完美，parent为父节点，curr为当前节点，n为总节点数
void dfs(vector<vector<int>>& adj, vector<int>& child_size, int parent, int curr, int n) {
    child_size[curr] = 1; //初始大小为1（自己也要存）
    bool perfect = true;  //flag
    
    //向下递归，计算子树大小
    for (auto child : adj[curr]) {
        if (parent == child) continue;
        dfs(adj, child_size, curr, child, n);
        child_size[curr] += child_size[child]; //累加子树大小
    }
    
    //检查所有子节点的子树大小
    for (auto child : adj[curr]) {
        if (parent == child) continue;
        //如果有一个子树大小是偶数，则不满足条件
        if (child_size[child] % 2 == 0) {
            perfect = false;
            break;
        }
    }
    
    //检查父节点方向的连通块大小
    if (n - child_size[curr] > 0 && (n - child_size[curr]) % 2 == 0) {
        perfect = false;
    }
    
    //满足条件
    if (perfect) {
        result++;
    }
}

void solve(int n) {
    result = 0;
    vector<vector<int>> adj(n + 1); //创建邻接表
    vector<int> child_size(n + 1, 0); //存储每个节点作为父亲的节点大小
    
    //读入边，存放如邻接表
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    //从节点1开始DFS
    dfs(adj, child_size, 0, 1, n);
    cout << result << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        solve(n);
    }
    return 0;
}

牛客周赛 Round 128 D. 小红的奇数奶油球