题解 | 小红的树

小红的树

https://www.nowcoder.com/practice/66ab364d3fba487eb39bd3460fd484c0

解题思路

核心思想：
- 使用DFS预处理每个节点的子树中红色节点数量
- 对于每次查询直接返回预处理的结果
实现步骤：
- 根据父节点数组构建树（邻接表）
- DFS遍历树，统计每个节点子树中的红色节点数
- 处理查询

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
vector<int> g[N];  // 邻接表
int count_red[N];  // 每个节点子树中的红色节点数
string colors;     // 节点颜色

int dfs(int u) {
    int total = (colors[u-1] == 'R');  // 当前节点是否为红色
    for(int v : g[u]) {
        total += dfs(v);
    }
    return count_red[u] = total;
}

int main() {
    int n;
    cin >> n;
    
    // 读入父节点数组并建图
    for(int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    
    // 读入颜色
    cin >> colors;
    
    // 预处理每个节点的子树红色节点数
    dfs(1);
    
    // 处理查询
    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        cout << count_red[x] << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static int N = 100010;
    static ArrayList<Integer>[] g;
    static int[] count;
    static String colors;
    
    static int dfs(int u) {
        int total = (colors.charAt(u-1) == 'R' ? 1 : 0);  // 当前节点是否为红色
        for(int v : g[u]) {
            total += dfs(v);
        }
        return count[u] = total;
    }
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 初始化
        g = new ArrayList[N];
        for(int i = 0; i < N; i++) {
            g[i] = new ArrayList<>();
        }
        count = new int[N];
        
        // 读入父节点数组并建图
        for(int i = 2; i <= n; i++) {
            int p = sc.nextInt();
            g[p].add(i);
        }
        
        // 读入颜色
        colors = sc.next();
        
        // 预处理每个节点的子树红色节点数
        dfs(1);
        
        // 处理查询
        int q = sc.nextInt();
        while(q-- > 0) {
            int x = sc.nextInt();
            System.out.println(count[x]);
        }
        
        sc.close();
    }
}


import sys
sys.setrecursionlimit(100010)

def dfs(u, g, color, count):
    """统计以u为根的子树中红色节点数"""
    total = 1 if color[u-1] == 'R' else 0  # 修正：索引从0开始
    for v in g[u]:
        total += dfs(v, g, color, count)
    count[u] = total
    return total

def main():
    # 输入
    n = int(input())
    parents = [1] + list(map(int, input().split()))  # 父节点数组
    colors = input()  # 节点颜色
    
    # 建图（子节点表示）
    g = [[] for _ in range(n + 1)]
    for i in range(2, n + 1):
        g[parents[i-1]].append(i)
    
    # 预处理每个节点的子树红色节点数
    count = [0] * (n + 1)
    dfs(1, g, colors, count)
    
    # 处理查询
    q = int(input())
    for _ in range(q):
        x = int(input())
        print(count[x])

if __name__ == "__main__":
    main()