给定一个包含 n
个节点的树,树的节点有两种颜色:红色(R)和黑色(B)。树的根节点为1号节点。每个节点的颜色由字符串 s
给出,s[i]
为 B
表示该节点颜色为黑色,为 R
则表示该节点颜色为红色。接下来,给定树的边,表示树的结构。
要求我们计算并输出有多少个子树中,既有红色节点(R)也有黑色节点(B)。
使用我们之前所学的深度优先搜索(DFS) 来遍历每个节点的子树,判断子树中是否存在红色和黑色的节点。
本题为2024年4月13日美团机考原题
美团机考的介绍点击这里
塔子哥有一棵有n个节点的树,根节点为1号节点,树的每个节点是红色或者黑色,她想知道有多少节点的子树中同时包含红点和黑点。
第一行输入一个整数n(1≤n≤105)表示节点数量 第二行输入一个长度为n的字符串s表示节点的颜色,第i个节点的颜色为si,若si为'B'表示节点的颜色为黑色,若si为'R' 则表示节点的颜色为红色。 接下来n−1行,每行输入两个整数 u,v(1≤u,≤n)表示树上的边.
输出一个整数表示答案。
输入
3
BRB
1 2
2 3
输出
2