小红拿到了一颗有根树树的根节点为1号节点。小红将一些节点染成了红色她想知道有多少子树满足子树所有节点均为红色。第一行输入一个正整数n代表节点的数量。第二行输入一个长度为n的字符串第i个字符为R代表第i个节点被染成红色为W代表未染色。接下来的n-1行每行输入两个正整数x和y代表x和y有一条连接。输出一个整数代表节点均为红色的子树个数。用c++实现

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; int n,ans; char c[maxn]; int head[maxn],tot; int f[maxn],dep[maxn],size[maxn],son[maxn]; struct edge { int next,to; }e[maxn<<1]; inline void add(int from,int to) { e[++tot].next=head[from]; e[tot].to=to; head[from]=tot; } void dfs1(int now,int fa) { dep[now]=dep[fa]+1; f[now]=fa; size[now]=1; for(int i=head[now];i;i=e[i].next) { int to=e[i].to; if(to==fa) continue; dfs1(to,now); size[now]+=size[to]; if(size[to]>size[son[now]]) son[now]=to; } } void dfs2(int now,int fa) { if(c[now]=='R') size[now]=1; else size[now]=0; for(int i=head[now];i;i=e[i].next) { int to=e[i].to; if(to==fa) continue; dfs2(to,now); size[now]+=size[to]; } if(size[now]==dep[now]-dep[fa]&&c[now]=='R') ans++; } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; add(x,y); add(y,x); } dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;i++) if(c[i]=='R'&&son[i]) ans++; cout<<ans<<endl; return 0; }