树形dp1

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Scanner;
/**
 * 小红拿到了一棵有根树。根节点为1号节点。
 * 所谓树，指没有回路的无向连通图。
 * 现在小红想给一部分点染成红色。之后她有 q\q 次询问，每次询问某点的子树红色节点的个数。
 *
 * 第一行一个正整数 nn ，代表树的节点个数。
 * 第二行有 n-1n−1 个正整数，分别表示第 22 个节点到第 nn 个节点每个节点的父亲。
 * 接下来一个长度为 nn 的、由'W'或'R'字符组成的字符串。第 ii 个字符为'W'代表该字符没被染色，若字符为'R'代表该字符被染成了红色。
 * 接下来一个正整数 qq ，代表小红的询问次数。
 * 接下来的 qq 行，每行有一个正整数 xx ，代表一次询问。
 * (1<= n,q <= 10^5,1 <= x <= n)(1≤n,q≤10
 * 5
 *  ,1≤x≤n)
 */
public class 树形dp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 用一个数组存每个节点的父亲节点
        int[] tree = new int[n+1];
        // 存总节点数
        tree[0] = n;
        // 根节点
        tree[1] = -1;
        // 构建树
        for (int i = 2; i <= n; i++) {
            tree[i] = sc.nextInt();
        }

        // 读取节点颜色标记
        char[] arr = sc.next().toCharArray();

        // dp[i]表示节点i的子树的红色节点个数
        int[] dp = new int[n+1];

        // 先记录所有的红色节点
        for (int i = 1; i <= n; i++) {
            if (arr[i-1] == 'R') {
                dp[i] = 1;
            }
        }
        // 再自底向上将子树的有色节点个数累加给父亲节点
        for (int i = n; i > 1; i--) {
            dp[tree[i]] += dp[i];
        }

        // 读取查询次数
        int q = sc.nextInt();
        while(q-- > 0) {
            int x = sc.nextInt();
            System.out.println(dp[x]);
        }
    }
}