题目描述

给定一棵 $n$ 个点的树。初始时刻为第 $0$ 秒，第 $i$ 个点的点权为 $a_i$。

从第 $0$ 秒到第 $1$ 秒、从第 $1$ 秒到第 $2$ 秒，以此类推：每经过 $1$ 秒，所有点同时将自己的点权变为变换前与该点距离不超过 $1$ 的所有点的点权最大值。

两点间的距离定义为它们之间简单路径经过的边数；特别地，一个点到自身的距离为 $0$。

给定整数 $k$，求最小的非负整数 $t$，使得第 $t$ 秒时所有点的点权之和不小于 $k$。

输入格式

第一行两个正整数 $n,k$。

第二行 $n$ 个正整数表示序列 $a_1,a_2,\dots,a_n$。

接下来 $n-1$ 行每行两个数表示树边。

输出格式

输出一行一个非负整数，表示所求的 $t$。

样例

4 11
1 3 2 1
1 2
2 3
2 4

1

样例解释

第 $0$ 秒时点权为 $1,3,2,1$，点权和为 $7$。

第 $1$ 秒时点权变为 $3,3,3,3$，点权和为 $12$，因此答案为 $1$。

数据规模与约定

本题共 20 个测试点，每个测试点 5 分。

特殊性质 A：$\max\limits_{1\le i\le n}a_i\le 2$。

特殊性质 B：给出的树是一条链。

对于全部测试数据，$1\le n\le 2\times 10^5$，$1\le a_i\le 20$，$1\le k\le n\max\limits_{1\le i\le n}a_i$。

保证输入的 $n-1$ 条边构成一棵树。

原题链接

原题链接