题解 | 小红的树

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] parents = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            parents[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer>[] children = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            children[i] = new ArrayList<>();
        }

        for (int j = 2; j <= n; j++) {
            int p = parents[j - 2];
            children[p].add(j);
        }

        String color = br.readLine();
        boolean[] red = new boolean[n + 1];
        for (int x = 1; x <= n; x++) {
            red[x] = color.charAt(x - 1) == 'R';
        }

        int[] redCount = new int[n + 1];
        Deque<Integer> nodeStack = new ArrayDeque<>();
        Deque<Boolean> processedStack = new ArrayDeque<>();
        nodeStack.push(1);
        processedStack.push(false);

        while (!nodeStack.isEmpty()) {
            int node = nodeStack.pop();
            boolean isProcessed = processedStack.pop();

            if (!isProcessed) {
                nodeStack.push(node);
                processedStack.push(true);
                List<Integer> childList = children[node];
                for (int i = childList.size() - 1; i >= 0; i--) {
                    int child = childList.get(i);
                    nodeStack.push(child);
                    processedStack.push(false);
                }
            } else {
                int cnt = red[node] ? 1 : 0;
                for (int child : children[node]) {
                    cnt += redCount[child];
                }
                redCount[node] = cnt;
            }
        }

        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int x = Integer.parseInt(br.readLine());
            sb.append(redCount[x]).append('\n');
        }
        System.out.print(sb);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：使用BufferedReader和StringTokenizer高效读取输入数据。
2. 树结构构建：根据父节点数组构建每个节点的子节点列表。
3. 颜色处理：将颜色字符串转换为布尔数组，标记每个节点是否为红色。
4. 后序遍历预处理：使用栈模拟后序遍历，计算每个节点的子树中红色节点的数量。每个节点在第一次访问时处理其子节点，第二次访问时累加子节点的红色节点数量。
5. 查询处理：预处理完成后，每个查询直接输出预处理的红色节点数量结果，使用StringBuilder缓存结果以减少IO次数。