曾经有一个名叫塔子哥的年轻人,他喜欢探索和解决各种难题。有一天,他发现了一棵神奇的树。树上已经有一些点被染成了红色,另一些点被染成了白色。
但是塔子哥想让相邻的两个点不能够颜色相同,因此他想知道最少需要进行多少次操作才能让树上所有相邻两个点的颜色不同,每次操作塔子哥可以选择一个点改变它的染色状态(红色变白色或者白色变红色)。
这个问题困扰着他很长一段时间,但是他决定不放弃,你能帮塔子哥想一想怎么解决这个问题吗?
第一行输入一个正整数 n ,代表节点的数量。
第二行输入一个长度为 n 的、仅由 'R'
、 'W'
两种字符组成的字符串,第 i 个字符为 'R'
代表 i 号节点被染成红色, 'W'
代表被染成白色。
接下来的 n−1 行,每行输入两个正整数 u 和 v ,代表节点 u 和节点 v 有一条路径相连。
1≤n≤105
1≤u,v≤n
一个整数,代表最小的操作次数。
输入
5
RRWWR
1 2
1 3
2 4
4 5
输出
2
样例解释
对 1 号和 3 号节点各操作一次即可。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.