UOJ Logo

NOI.AC

1S 512MB

#774. b

Statistics

小z有一棵 n 个点的树,每个点有个点权 $V_i$。小z可以选择一些不相交的路径去覆盖一些点,如果他覆盖了权值和为 S 的点,共用了 K 条路径,则最终收获就是 $\frac{S}{K+1}$。

贪婪的小z为了收获更多会在一开始修改点权,他可以选择一个 0 到 T 中间的整数 C,所有点的点权都会加上 C,不过,所有点的点权都会对一个整数 Limit 取模,即变成 $(V_i+C) \pmod{Limit}$。小z想知道他最大的收获是多少。

输入格式

第一行两个整数 n 和 Limit。

接下来一行 n 个整数 $V_i$。

接下来 n-1 行,每行两个整数 $u_i,v_i$,表示这棵树。

最后一行一个整数 $T$,表示修改范围。

输出格式

一行一个实数,表示答案,当你的答案与标准答案绝对误差不超过 $10{-6}$ 可以获得满分。

样例数据

输入样例一

4 100
1 1 1 1
1 2
1 3
1 4
0

输出样例一

1.5

数据规模与约定

本题采用捆绑测试

对于 15 分的数据,$n \le 2000,T=0$;

对于另外 15 分的数据,$n \le 2000,Limit \le 100$;

对于另外 30 分的数据,$n\le 1000$

对于所有的数据, $n\le 5000,V_i,T < Limit \le 10^6$。

时间限制:$1\text{s}$

空间限制:$512\text{MB}$