小红的红子树

小红拿到了—棵有根树，树的根节点为1号节点。

小红将一些节点染成了红色。她想知道有多少子树满足子树所有节点均为红色?

输入描述

第一行输入一个正整数n，代表节点的数量。

第二行输入一个长度为n的字符串，第i个字符为'R'代表第i个节点被染成红色，为'w'代表未被染色。

接下来的n ― 1行，每行输入两个正整数x和y，代表x和y有一条边连接。

1<n≤105

1 ≤x, y ≤n

输出描述

输出一个整数，代表节点均为红色的子树数量。

示例1

输入输出示例仅供调试，后台判题数据─般不包含示例

输入

3

WRR

1 2

1 3

输出

2

说明

节点2和节点3均合法

思路

在这道题中，我们采用字典的这种方式去存储图，记录每一个点的相邻节点。但要注意一点的是在递归的时候不可以调用他的父节点，否则会发生栈溢出。

在深度搜索过程中，我们先判断当前节点是否为红，再将这一判断结果cur与递归结果做&&运算，（注：递归函数最后要返回cur值），这样就可以判断以当前节点为根节点的子树是否是否全部为红色，如果全为红，则将结果+1。这样我们就能得到本题的答案了。

1. n=int(input()) 2. colors="0"+input() 3. dir1={} 4. for i in range(n-1): 5. x,y=map(int,input().split(" ")) 6. if x not in dir1: dir1[x]=[] 7. if y not in dir1: dir1[y]=[] 8. dir1[x].append(y) 9. dir1[y].append(x) 10. 11. cnt=0 12. def dfs(node,pre): 13. cur = (colors[node]=='R') 14. for nx in dir1[node]: 15. # nx点和pre点是相连的，我们不能去递归nx的父节点，否则产生深度溢出 16. if nx!=pre: 17. cur = dfs(nx,node) and cur 18. global cnt 19. if cur:cnt+=1 20. return cur 21. 22. 23. dfs(1,-1) 24. print(cnt)