题解 | #小红的树#

解题思路：

• 所有节点构成一个树，是无回路的无向图，但在这题中只要记录从根节点到叶节点方向的路径，使用链接前向星建立图。对于任一结点 $nod{e}_i,i\in [1,n]node\_i,\; i\; \backslash in\; [1,n]$,计算以该节点为root的子树中红色节点的个数，只要递归计算出其子树的红色节点个数以及其自己是否为红色即可。
• 令$d{p}_{i}dp\_i$为以$ii$为root的子树所包含的红色节点数，可以得出$d{p}_i=d{p}_j+colo{r}_{i}is{}^{\mathrm{\prime }}Re{d}^{\mathrm{\prime }},j\in roo{t}_i^{\mathrm{\prime }}ssondp\_i\; =\; dp\_j\; +\; color\_i\backslash \; is\; \backslash \; \text{'}Red\text{'},\; j\; \backslash in\; root\_i\text{'}s\; \backslash \; son$，递归过程中使用记忆化搜索。
• 该题可以一次搜索，多次查询，搜索所需要的时间应为$O(n)O(n)$,所有的节点只遍历一遍。查询的时间复杂度是$O(1)O(1)$。

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int to, next;
} es[100005];
int cnt = 0;
int head[100005];
char color[100005];
int dp[100005];
void add_edge(int from, int to)
{
    es[++cnt].to = to;
    es[cnt].next = head[from];
    head[from] = cnt;
}
int solve(int i)
{
    if (dp[i] != -1)
        return dp[i];
    if (head[i] == 0)
        dp[i] = color[i] == 'R' ? 1 : 0;
    else
    {
        if (dp[i] == -1)
            dp[i] = color[i] == 'R';
        for (int j = head[i]; j != 0; j = es[j].next)
            dp[i] += solve(es[j].to);       
    }
    
    return dp[i];
}
int main()
{
    int n;
    cin >> n;
    int tmp;
    memset(dp, -1, sizeof(dp));
    for (int i = 2; i <= n; ++i)
    {
        scanf("%d", &tmp);
        add_edge(tmp, i);
    }
    scanf("%s", color + 1);
    solve(1);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        cin >> tmp;
        cout << dp[tmp] << endl;
    }

    return 0;
}