描述

给一棵根为$11$的树，树上部分节点被染色，$qq$次询问，每次询问某个节点的子树中有多少被染色的结点

思路

• 树形DP模板题，设$dp[i]dp[i]$为节点$ii$为根的子树有多少节点被染色，初始化时，如果节点$ii$被染色，则$dp[i]=1dp[i]=1$否则为$00$
• 转移方程为 $dp[i]=dp[i]+{\sum }_{j\mathrm{是}i\mathrm{的}\mathrm{儿}\mathrm{子}}dp[j]dp[i]=dp[i]+\backslash sum\_\{j是i的儿子\}dp[j]$

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
char s[MAXN];
vector<int> E[MAXN];
int dp[MAXN];
void dfs(int now)
{
    if(s[now]=='R')
        dp[now]++;
    for(int v:E[now])
    {
        dfs(v);
        dp[now]+=dp[v];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int fa;
        scanf("%d",&fa);
        E[fa].push_back(i);
    }
    scanf("%s",s+1);
    dfs(1);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",dp[x]);
    }
}

时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$