#icpc2015springa. [icpc2015spring_a]Balanced Paths
[icpc2015spring_a]Balanced Paths
题目描述:
您有一个 个结点的无向树,结点编号为 到 。每个节点都标有 (
或 )
的标签。 表示连接从 到 的路径上结点的标签所获得的字符串(请注意:两个结点之间的路径在树上是唯一确定的)。平衡字符串的定义如下:
- 空字符串是平衡的。
- 对于任何平衡字符串
s
,字符串(s)
是平衡的。 - 对于任何平衡字符串
s
和t
,字符串st
是平衡的。 - 只有上述三种字符串是平衡的,其他的不是平衡的。
请问有多少有序数对 满足 是平衡的。
输入:
输入由单个测试用例组成。
输入一个整数 (),即树的结点数。
下一行包含长度为 的字符串,其每个字符为 (
或 )
。字符串的第 个字符表示树的结点 的标签。
接下来 行,每行包含两个整数 和 (),表示结点 和结点 间有一条边。给定的图保证为树。
输出:
输出有序数对个数。