很久很久以前,在一个古老的山林里,生长着一棵神奇的树,这棵树生长得异常高大,分布着数不清的分枝和树叶,形成了一片繁盛的生态系统。
这棵树的主人,是一个叫做塔子哥的年轻人。他是这个山林里唯一一个会看护这棵树的人,他每天都会来到这里,仔细观察着这棵树的每一个角落。这些日子里,塔子哥发现这棵树非常特别,因为这棵树上的每个节点都被染成了红色或者蓝色。
他很好奇这棵树的奥秘,于是他决定对这棵树进行深入研究。在经过长时间的观察和思考后,塔子哥发现了这棵树的一个重要性质:删除树上的任意一条边,都会导致树被分成两个子树。
同时,对于每个子树,如果子树中有一些节点颜色相同且连通,那么这些节点就形成了一个同色连通块。例如,一棵子树中有两个红色节点相连,这两个节点就形成了一个红色连通块。
于是,塔子哥定义了一条边的权值为:删除这条边时,形成的两个子树的同色连通块数量之差的绝对值。他想知道,所有边的权值之和是多少?
第一行输入一个正整数 n ,代表节点的数量。
第二哈输入一个长度为 n 且仅由 R 和 B 两种字符组成的字符串。
第 i 个字符为 R 代表 i 号节点被染成红色,为 B 则被染成蓝色。
接下来的 n−1 行,每行输入两个正整数 u 和 v ,代表节点 u 和节点 v 有一条边相连。
1≤n≤200000
一个正整数,代表所有节点的权值之和。
输入
5
BRRBB
1 2
2 3
1 4
4 5
输出
3
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.