本题其实就是统计子树中有多少个节点既有红色节点,又有黑色节点。我们可以自顶向下来进行DFS
遍历到u节点时,首先根据u节点是红/黑,来对变量进行初始化
然后我们可以遍历u的所有子节点,去将以u为根节点的红/黑节点数量进行累加计算。
最后判断以u为子树的根节点的红色和黑色节点数量是否都大于0,若大于0,则答案+1
小美有一棵有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