描述
给一棵根为的树,树上部分节点被染色,次询问,每次询问某个节点的子树中有多少被染色的结点
思路
- 树形DP模板题,设为节点为根的子树有多少节点被染色,初始化时,如果节点被染色,则否则为
- 转移方程为
代码
#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]);
}
}
时间复杂度,空间复杂度