解题思路

1. 问题理解

• 有一棵 $n$ 个节点的树，每个节点颜色是 B（黑）或 R（红）。
• 路径上相邻两个节点颜色不同，则该路径是 颜色交错路径。
• 单节点路径也算颜色交错路径。
• 要求统计所有颜色交错的简单路径的条数。

题目内容

小美有一棵由$n$个节点组成的树，每个节点被涂为红色或黑色。她想统计树中有多少条颜色交错的简单路径。

路径是指任意两个节点之间的唯一简单路径，并且我们也将单个节点自身视为长度为$1$的路径。若一条路径上任意相邻的两个节点颜色不同，则称该路径为颜色交错的路径。

请计算树中颜色交错的路径总数。

[名词解释]

树上的路径：从节点u到节点v的简单路径定义为从节点$u$出发，以节点$v$为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。

输入描述

第一行输入一个整数$n(1≦n≦2×105)$，表示树的节点数量。

接下来$n-1$行，每行输入两个整数$u$和$v (1≦u,v ≦n;u≠v)$，表示节点$u$与$v$之间有一条无向边。保证输入构成一棵树。

接下来一行，输入一个长度为$n$的字符串$s$，仅由字符$B$和$R$构成，其中$s_i=B$表示第$i$个节点为黑色;$s_i=R$表示红色。

输出描述

输出一个整数，表示树中颜色交错的路径总数。

样例1

输入

6
1 2
2 3
3 4
4 5
3 6
BRBRBB

输出

16

说明

这棵树共有$16$条颜色交错的路径(包括$6$条单节点路径、$4$条长度为$2$的路径、$3$条长度为$3$的路径、$2$条长度为$4$的路径、$1$条长度为$5$的路径)。

样例2

输入

3 
1 2
2 3
BBB

输出

3

说明

只有单节点路径满足颜色交错，共$3$条。