题解 | 小红的树

import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int subTreePoints[] = new int[100000+1];
    public static int BFS(Object[] treeNodes, int nodeId, int[] color) {
        int ret = 0;
        ArrayList<Integer> allNotes = new ArrayList<>();
        

        //ret = color[nodeId];
        allNotes.add(nodeId);
        while(!allNotes.isEmpty()) {
            int id = allNotes.remove(0);

            if (subTreePoints[id] > 0) {
                ret += subTreePoints[id];
                continue;
            }


            ret += color[id];

            ArrayList<Integer> children = (ArrayList<Integer>)treeNodes[id];

            if (children != null) {
                allNotes.addAll(children);
            }

            //System.out.println(allNotes);
            
        }

        subTreePoints[nodeId] = ret;

        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Object[] treeNodes = new Object[100000+1];
        int color[] = new int[n + 1];

        for(int i = 2; i <= n; i++) {
            int fatherId = in.nextInt();
            ArrayList<Integer> children = (ArrayList<Integer>)treeNodes[fatherId];
            if (children == null) {
                children = new ArrayList<Integer>();
                treeNodes[fatherId] = children;
            }
            children.add(i);
            
        }

        // for(Object c : treeNodes) {
        //     System.out.println((ArrayList<Integer>)c);
        // }
        

        String str = in.next();
        for(int i = 1; i <= n; i++) {
            color[i] = str.charAt(i - 1) == 'W' ? 0 : 1;
        }

        in.nextInt();
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            //int b = in.nextInt();
            System.out.println(BFS(treeNodes, a, color));
        }
    }
}

思路：自顶向下的动态规划。