题目内容

很久很久以前，在一个古老的山林里，生长着一棵神奇的树，这棵树生长得异常高大，分布着数不清的分枝和树叶，形成了一片繁盛的生态系统。

这棵树的主人，是一个叫做塔子哥的年轻人。他是这个山林里唯一一个会看护这棵树的人，他每天都会来到这里，仔细观察着这棵树的每一个角落。这些日子里，塔子哥发现这棵树非常特别，因为这棵树上的每个节点都被染成了红色或者蓝色。

他很好奇这棵树的奥秘，于是他决定对这棵树进行深入研究。在经过长时间的观察和思考后，塔子哥发现了这棵树的一个重要性质：删除树上的任意一条边，都会导致树被分成两个子树。

同时，对于每个子树，如果子树中有一些节点颜色相同且连通，那么这些节点就形成了一个同色连通块。例如，一棵子树中有两个红色节点相连，这两个节点就形成了一个红色连通块。

于是，塔子哥定义了一条边的权值为：删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。他想知道，所有边的权值之和是多少？

输入描述

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

第二哈输入一个长度为 $n$ 且仅由 $R$ 和 $B$ 两种字符组成的字符串。

第 $i$ 个字符为 $R$ 代表 $i$ 号节点被染成红色，为 $B$ 则被染成蓝色。

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

$1\le n\le 200000$

输出描述

一个正整数，代表所有节点的权值之和。

样例

输入

5
BRRBB
1 2
2 3
1 4
4 5

输出

3