小红拿到了一棵有根树，树的根节点为1号节 点。 小红将一些节点染成了红色。她想知道有多少子 树满足子树所有节点均为红色？

我们可以使用深度优先搜索（DFS）来遍历整棵树。对于每个节点，我们可以记录它的子树中红色节点的数量。如果当前节点是红色的，那么它的子树中所有节点都是红色的，因此子树中红色节点的数量为它的子树大小。否则，子树中红色节点的数量为0。

最后，我们可以再次遍历整棵树，对于每个节点，如果它是红色的并且它的父节点也是红色的，则它所在的子树也是红色的，因此可以将它的子树大小加入答案中。

时间复杂度：O(n)，其中n为节点数。

相关问题

"节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。 给你一棵n个节点的有根树，节点标号为1~n，1号节点为根节点。特别的，每个点的子节点个数不超过5。 请你输出该树中偶点的个数。 输入 第一行一个整数n。 以后n行，每行若干个整数。第i行，第一个数为mi，表示节点i的子节点个数。紧接着mi个整数，表示节点i子节点的编号。保证父节点编号小于子节点。 输出 一行一个整数，表示偶点个数c++代码。

你可以使用以下的C++代码来求解该问题：

#include <iostream>
#include <vector>

using namespace std;

int countEvenNodes(vector<vector<int>>& tree, int node) {
    int count = 0;
    if (tree[node].size() % 2 == 0) {
        count++;
    }
    for (int child : tree[node]) {
        count += countEvenNodes(tree, child);
    }
    return count;
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> tree(n + 1);
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        tree[parent].push_back(i);
    }

    int evenNodes = countEvenNodes(tree, 1);
    cout << evenNodes << endl;

    return 0;
}

这段代码首先读取输入的整数n，表示树的节点个数。接下来的n行，每行先读取一个整数mi，表示节点i的子节点个数，然后读取mi个整数，表示节点i的子节点编号。

代码中的`countEvenNodes`函数用于递归地计算以当前节点为根的子树中偶点的个数。如果当前节点的子节点个数为偶数，那么当前节点也算作一个偶点。然后，对当前节点的每个子节点进行递归调用，并将子树中的偶点个数累加到count中。

最后，在主函数中创建一个二维向量tree来表示树的结构。根据输入构建树的结构，然后调用`countEvenNodes`函数计算偶点的个数，并输出结果。

希望这个代码对你有帮助！

"节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。 给你一棵n个节点的有根树，节点标号为1~n，1号节点为根节点。特别的，每个点的子节点个数不超过5。 请你输出该树中偶点的个数。 输入 第一行一个整数n。 以后n行，每行若干个整数。第i行，第一个数为mi，表示节点i的子节点个数。紧接着mi个整数，表示节点i子节点的编号。保证父节点编号小于子节点。 输出 一行一个整数，表示偶点个数。c++代码

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

vector<int> degrees;
vector<vector<int>> tree;

void dfs(int node) {
    int degree = tree[node].size();
    degrees[node] = degree;
    for (int child : tree[node]) {
        dfs(child);
    }
}

int main() {
    int n;
    cin >> n;
    
    tree.resize(n + 1);
    degrees.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        
        for (int j = 0; j < m; j++) {
            int child;
            cin >> child;
            
            tree[i].push_back(child);
        }
    }
    
    dfs(1);
    
    int evenCount = 0;
    for (int i = 1; i <= n; i++) {
        if (degrees[i] % 2 == 0) {
            evenCount++;
        }
    }
    
    cout << evenCount << endl;
    
    return 0;
}

这段代码通过深度优先搜索（DFS）遍历树，计算每个节点的度，并统计偶点的个数。首先，我们定义了一个 `degrees` 数组来保存每个节点的度。然后，我们使用一个二维向量 `tree` 来表示树的结构，其中 `tree[i]` 表示节点 i 的子节点列表。在主函数中，我们首先读取输入数据，构建树的结构。然后，我们调用 `dfs` 函数开始深度优先搜索，从根节点开始遍历，并将每个节点的度记录在 `degrees` 数组中。最后，我们遍历 `degrees` 数组，统计偶点的个数并输出。