A186077.星树密语

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一棵星树共有 nn 个节点,编号为 1∼n1\sim n,以 11 号节点为根。每个节点上刻着一个左括号 ( 或右括号 )。

从根节点出发,沿树向下走到某个叶子,依次读出经过的所有节点上的括号,包括根节点和叶子节点上的括号,就得到一条密语。

一个括号序列称为合法序列,当且仅当:

  • 任意前缀中,左括号数量都不少于右括号数量;
  • 整个序列中,左括号数量等于右括号数量。

合法括号序列的嵌套深度,等于所有前缀中“左括号数量减去右括号数量”的最大值。例如,()() 的嵌套深度为 11,(()) 的嵌套深度为 22。

现在给出一个整数 KK。请你统计有多少个叶子,使得从根到它的密语是合法括号序列,并且嵌套深度不超过 KK。

叶子指以 11 号节点为根时,没有孩子的节点。当 n=1n=1 时,根节点也是叶子。不同叶子分别计数,即使它们对应的括号序列完全相同。

输入格式

第一行输入两个整数 n,Kn,K,分别表示节点数和允许的最大嵌套深度。

第二行输入一个长度为 nn 的字符串 ss,只包含 ( 和 ),第 ii 个字符表示节点 ii 上的括号。字符串中没有空格。

接下来 n−1n-1 行,每行输入两个整数 u,vu,v,表示节点 uu 与节点 vv 之间有一条无向边。

输出格式

输出一个整数,表示满足条件的叶子数量。

输入输出样例

  • 输入#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,82,5,8。

  • 路径 1→21\to2 对应 (),合法且深度为 11;
  • 路径 1→3→4→51\to3\to4\to5 对应 (()),合法但深度为 22,超过 KK;
  • 路径 1→6→7→81\to6\to7\to8 对应 ()(),合法且深度为 11。

因此答案为 22。

样例解释 2

唯一的根到叶子路径只包含一个左括号,不是合法括号序列。

数据范围

对于所有测试数据,保证:

  • 1≤n≤2×1051\le n\le2\times10^5;
  • 1≤K≤n1\le K\le n;
  • ∣s∣=n|s|=n,且 ss 仅包含 ( 和 );
  • 1≤u,v≤n1\le u,v\le n,u≠vu\ne v;
  • 输入的边将全部节点连成一棵树,没有重边;
  • 不保证存在满足条件的叶子。

输入解题思路,AI测评打分。不知道怎么写?

首页