#icpc2015springa. [icpc2015spring_a]Balanced Paths

[icpc2015spring_a]Balanced Paths

题目描述:

您有一个 nn 个结点的无向树,结点编号为 11nn。每个节点都标有 () 的标签。l[uv]l[u\rightarrow v] 表示连接从 uuvv 的路径上结点的标签所获得的字符串(请注意:两个结点之间的路径在树上是唯一确定的)。平衡字符串的定义如下:

  • 空字符串是平衡的。
  • 对于任何平衡字符串 s,字符串 (s) 是平衡的。
  • 对于任何平衡字符串 st,字符串 st 是平衡的。
  • 只有上述三种字符串是平衡的,其他的不是平衡的。

请问有多少有序数对 (u,v)(u,v) 满足 l[uv]l[u\rightarrow v] 是平衡的。

输入:

输入由单个测试用例组成。

输入一个整数 nn2n1052\le n\le105),即树的结点数。

下一行包含长度为 nn 的字符串,其每个字符为 ()。字符串的第 xx 个字符表示树的结点 xx 的标签。

接下来 n1n-1 行,每行包含两个整数 aia_ibib_i1ai,bin1\le a_i,b_i\le n),表示结点 aia_i 和结点 bib_i 间有一条边。给定的图保证为树。

输出:

输出有序数对个数。