P3345.第3题-树上的路径
题目内容
小美有一棵由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构成，其中si=B表示第i个节点为黑色;si=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条。
