#P6655. [2019雅礼集训]bracket

    ID: 6505 传统题 1000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理一维前缀和树算法点分治点分治容斥去重多项式与生成函数卷积转化NTT数论中国剩余定理组合数学补集计数CF2800

[2019雅礼集训]bracket

[2019雅礼集训]bracket

题目描述

给定一棵有 nn 个节点的无根树,每个节点有一个字符,为 ( 或 )。

定义 S(x,y)S(x,y) 为沿树上从节点 xx 到节点 yy 的简单路径,依次连接经过的所有节点字符得到的字符串,包含两个端点的字符。路径有方向,S(x,y)S(x,y) 与 S(y,x)S(y,x) 可能不同。

非空合法括号序列定义如下:

  1. () 是合法括号序列。
  2. 若 AA 合法,则在其两侧加上括号得到的 (A)(A) 也合法。
  3. 若 A,BA,B 分别合法,则连接得到的 ABAB 也合法。

若 S(x,y)S(x,y) 合法,将它划分为若干个连续、非空的合法括号序列,定义 f(x,y)f(x,y) 为最多可以划分成的段数。例如,(())()() 的最大段数是 33,(()())(()) 的最大段数是 22。

若 S(x,y)S(x,y) 本身不是合法括号序列,则定义 f(x,y)=0f(x,y)=0。

有 mm 次询问,每次给出整数 kk,求满足 f(x,y)=kf(x,y)=k 的点对 (x,y)(x,y) 数量。

输入格式

第一行一个正整数 nn。

接下来 n−1n-1 行,每行两个整数 x,yx,y,表示一条树边。节点编号为 11 到 nn。

接下来 nn 行,每行一个字符 ( 或 ),第 ii 行表示节点 ii 的字符。

接下来一行一个正整数 mm,表示询问数。

接下来 mm 行,每行一个整数 kk,表示一次询问。

输出格式

输出 mm 行,每行一个整数,表示对应询问中满足 f(x,y)=kf(x,y)=k 的点对数量。

样例输入

6
1 2
2 6
4 2
3 4
1 5
)
(
)
)
(
)
3
1
2
3

样例输出

4
2
0

数据范围

数据比例 附加限制
10%10\% n,m≤100n,m\le100
30%30\% n,m≤5000n,m\le5000
另 30%30\% m≤10m\le10
100%100\% 1≤n,m≤500001\le n,m\le50000