【深度优先搜索6】塔子哥的红黑树

题面简述

给定一个包含 n 个节点的树，树的节点有两种颜色：红色(R)和黑色(B)。树的根节点为1号节点。每个节点的颜色由字符串 s 给出，s[i] 为 B 表示该节点颜色为黑色，为 R 则表示该节点颜色为红色。接下来，给定树的边，表示树的结构。

要求我们计算并输出有多少个子树中，既有红色节点(R)也有黑色节点(B)。

解题思路

使用我们之前所学的深度优先搜索（DFS） 来遍历每个节点的子树，判断子树中是否存在红色和黑色的节点。

本题为2024年4月13日美团机考原题

美团机考的介绍点击这里

题目描述

塔子哥有一棵有$n$个节点的树，根节点为1号节点，树的每个节点是红色或者黑色，她想知道有多少节点的子树中同时包含红点和黑点。

输入描述

第一行输入一个整数$n(1\le n\le 10^5)$表示节点数量 第二行输入一个长度为$n$的字符串$s$表示节点的颜色，第$i$个节点的颜色为$s_i$，若$s_i$为'B'表示节点的颜色为黑色，若$s_i$为'R' 则表示节点的颜色为红色。 接下来$n -1$行，每行输入两个整数 $u,v(1\le u,\le n)$表示树上的边.

输出描述

输出一个整数表示答案。

样例

输入

3
BRB
1 2
2 3

输出

2