树上移动(8级)

题意概述

给定一棵含有 \(n\) 个节点的树（节点编号 \(1\sim n\)）。每个节点被染成白色或黑色。你可以任选起点 \(s\) 和终点 \(t\)，沿树上的简单路径（不经过重复节点）从 \(s\) 走到 \(t\)。

要求在经过的黑色节点数不超过 \(k\)（包含端点）的前提下，使路径上经过的节点总数尽可能大。请输出能达到的最大节点数。

注：树上任意两点间的简单路径唯一；"经过的节点数"指路径上不同节点的个数。

输入格式

• 第一行：两个整数 \(n,k\)——节点数与允许经过的黑色节点上限。
• 第二行：\(n\) 个整数 \(a_1,a_2,\dots,a_n\)，表示每个节点的颜色： \(a_i=0\) 为白色，\(a_i=1\) 为黑色。
• 接下来 \(n-1\) 行：每行两个整数 \(u_i,v_i\)，表示树的一条无向边 \(u_i\text{—}v_i\)。

输出格式

输出一个整数，表示在"黑色节点数 \(\le k\)"约束下，能经过的最大节点数。

样例

输入

5 1
0 0 1 1 1
1 2
2 3
2 5
1 4

输出

3

说明与提示

• 对于全部数据：\(1\le n\le 1000\)，\(0\le k\le 1000\)，\(0\le a_i\le 1\)。
• 黑色节点计数包含路径两端点在内。