思路

解法1:树形dp

树上dp.$dp_{i,j}$ 代表以$i$为根，且$color(i)$ 是$red/white$ 下的最优解。转移为:

题目内容

曾经有一个名叫小红的年轻人，他喜欢探索和解决各种难题。有一天，他发现了一棵神奇的树。树上已经有一些点被染成了红色，另一些点被染成了白色。

但是小红想让相邻的两个点不能够颜色相同，因此他想知道最少需要进行多少次操作才能让树上所有相邻两个点的颜色不同，每次操作小红可以选择一个点改变它的染色状态（红色变白色或者白色变红色）。

这个问题困扰着他很长一段时间，但是他决定不放弃，你能帮小红想一想怎么解决这个问题吗？

输入描述

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

第二行输入一个长度为 $n$ 的、仅由 'R' 、 'W' 两种字符组成的字符串，第 $i$ 个字符为 'R' 代表 $i$ 号节点被染成红色， 'W' 代表被染成白色。

接下来的 $n-1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表节点 $u$ 和节点 $v$ 有一条路径相连。

$1\le n\le 10^5$

$1\le u,v\le n$

输出描述

一个整数，代表最小的操作次数。

样例

输入

5
RRWWR
1 2
1 3
2 4
4 5

输出

2

样例解释

对 $1$ 号和 $3$ 号节点各操作一次即可。