A186077.星树密语
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一棵星树共有 n 个节点,编号为 1∼n,以 1 号节点为根。每个节点上刻着一个左括号 ( 或右括号 )。
从根节点出发,沿树向下走到某个叶子,依次读出经过的所有节点上的括号,包括根节点和叶子节点上的括号,就得到一条密语。
一个括号序列称为合法序列,当且仅当:
- 任意前缀中,左括号数量都不少于右括号数量;
- 整个序列中,左括号数量等于右括号数量。
合法括号序列的嵌套深度,等于所有前缀中“左括号数量减去右括号数量”的最大值。例如,()() 的嵌套深度为 1,(()) 的嵌套深度为 2。
现在给出一个整数 K。请你统计有多少个叶子,使得从根到它的密语是合法括号序列,并且嵌套深度不超过 K。
叶子指以 1 号节点为根时,没有孩子的节点。当 n=1 时,根节点也是叶子。不同叶子分别计数,即使它们对应的括号序列完全相同。
输入格式
第一行输入两个整数 n,K,分别表示节点数和允许的最大嵌套深度。
第二行输入一个长度为 n 的字符串 s,只包含 ( 和 ),第 i 个字符表示节点 i 上的括号。字符串中没有空格。
接下来 n−1 行,每行输入两个整数 u,v,表示节点 u 与节点 v 之间有一条无向边。
输出格式
输出一个整数,表示满足条件的叶子数量。
输入输出样例
输入#1
8 1 ()()))() 1 2 1 3 3 4 4 5 1 6 6 7 7 8
输出#1
2
输入#2
1 1 (
输出#2
0
说明/提示
样例解释 1
叶子节点为 2,5,8。
- 路径 1→2 对应
(),合法且深度为 1; - 路径 1→3→4→5 对应
(()),合法但深度为 2,超过 K; - 路径 1→6→7→8 对应
()(),合法且深度为 1。
因此答案为 2。
样例解释 2
唯一的根到叶子路径只包含一个左括号,不是合法括号序列。
数据范围
对于所有测试数据,保证:
- 1≤n≤2×105;
- 1≤K≤n;
- ∣s∣=n,且 s 仅包含
(和); - 1≤u,v≤n,u=v;
- 输入的边将全部节点连成一棵树,没有重边;
- 不保证存在满足条件的叶子。
输入解题思路,AI测评打分。不知道怎么写?