题目描述

不要小看噜噜哦，它什么都会！在一片辽阔的森林中，护林员噜噜每天都会从某个哨点出发，沿着林区中的林道前行，直到到达终点哨点。

林道系统可以抽象成一棵有 $N$ 个哨点节点（编号为 $1\ldots N$）的树形结构。为了防止火灾蔓延，森林部门在部分哨点上安装了监测仪（称为“高危哨点”），经过这些哨点需要格外小心，耗时更长。

为了让护林员安全且尽可能多覆盖哨点，噜噜希望选择一条从哨点 $S$ 到哨点 $T$ 的简单路径（树中没有重复节点），并且这条路径上经过的“高危哨点”数量不超过 $K$，使得路径上经过的节点总数尽可能多。

给定一棵包含 $N$ 个节点的树（哨点），节点编号为 $1$ 到 $N$。每个节点要么是“普通哨点”（记作 0），要么是“高危哨点”（记作 1）。护林员可以任选起点哨点 $S$ 和终点哨点 $T$，并沿唯一的简单路径从 $S$ 行驶到 $T$。要求这条路径上所经过（包含 $S$ 和 $T$）的“高危哨点”数量不超过 $K$，并使得路径上的节点总数（包含 $S$ 和 $T$）最大。

请计算在此约束下，护林员最多可以经过多少个哨点。

输入格式

1. 第一行包含两个整数 $\,N$,$\,K$，分别表示哨点数量与路径上允许经过的“高危哨点”上限。
2. 第二行是一个长度恰好为 $N$ 的二进制字符序列 $s$，每个字符为 0 或 1。其中第 $i$ 个字符如果是 0 ，表示第 $i$ 个哨点为普通哨点；如果是 1，表示第 $i$ 个哨点为高危哨点。
3. 接下来 $N-1$ 行，每行包含两个整数 $u$，$v$，表示哨点 $u$ 和 $v$ 之间存在一条无向边（林道），保证这些边构成一棵连通树。

输出格式

输出一个正整数，表示在允许经过不超过 $K$ 个高危哨点的前提下，护林员所能选择的路径上节点数的最大值。

6 2
010110
1 2
1 3
2 4
2 5
3 6

5

样例解释

• 第一行 6 2 表示共有 6 个哨点，最多可经过 2 个高危哨点。

• 第二行 010110 表示：

  • 哨点 1 为 0（普通）；
  • 哨点 2 为 1（高危）；
  • 哨点 3 为 0（普通）；
  • 哨点 4 为 1（高危）；
  • 哨点 5 为 1（高危）；
  • 哨点 6 为 0（普通）。

• 边集如下：

  1–2
  1–3
  2–4
  2–5
  3–6
  

  其示意图（括号内带数字表示“颜色”：$0 =$ 普通 $1 =$ 高危）：

        1(0)
       /   \
     2(1)   3(0)
    /   \     \
  4(1) 5(1)   6(0)
  

• 允许路径上高危哨点 $\le 2$。

• 可以选择路径 4 – 2 – 1 – 3 – 6，其节点为 $\{4(1), 2(1), 1(0), 3(0), 6(0)\}$，其中高危哨点数 $= 2$，节点总数 $= 5$，合法。

• 也可以选 5 – 2 – 1 – 3 – 6，同理高危哨点 $\{5,2\}$ 共 $2$ 个，节点数 $5$。

• 任何更长路径要么不连通，要么高危哨点数 $> 2$。

• 因此答案为 $5$。

数据规模与约定

• 对于所有测试点，保证

  $$ 1 \le N \le 2\times10^5,\quad 0 \le K \le 2\times10^5,\quad s_i \in \{0,1\}. $$

• 树上节点编号 $1\ldots N$，边以无向方式连接，保证输入构成一棵连通树。