#P6655. [2019雅礼集训]bracket
[2019雅礼集训]bracket
[2019雅礼集训]bracket
题目描述
给定一棵有 个节点的无根树,每个节点有一个字符,为 ( 或 )。
定义 为沿树上从节点 到节点 的简单路径,依次连接经过的所有节点字符得到的字符串,包含两个端点的字符。路径有方向, 与 可能不同。
非空合法括号序列定义如下:
()是合法括号序列。- 若 合法,则在其两侧加上括号得到的 也合法。
- 若 分别合法,则连接得到的 也合法。
若 合法,将它划分为若干个连续、非空的合法括号序列,定义 为最多可以划分成的段数。例如,(())()() 的最大段数是 ,(()())(()) 的最大段数是 。
若 本身不是合法括号序列,则定义 。
有 次询问,每次给出整数 ,求满足 的点对 数量。
输入格式
第一行一个正整数 。
接下来 行,每行两个整数 ,表示一条树边。节点编号为 到 。
接下来 行,每行一个字符 ( 或 ),第 行表示节点 的字符。
接下来一行一个正整数 ,表示询问数。
接下来 行,每行一个整数 ,表示一次询问。
输出格式
输出 行,每行一个整数,表示对应询问中满足 的点对数量。
样例输入
6
1 2
2 6
4 2
3 4
1 5
)
(
)
)
(
)
3
1
2
3
样例输出
4
2
0
数据范围
| 数据比例 | 附加限制 |
|---|---|
| 另 | |