题目背景
What did this player dream?
他梦见了什么?
This player dreamed of sunlight and trees.Of fire and water.
他梦见了阳光与树木。梦见了火与水。
It dreamed it created. And it dreamed it destroyed. It dreamed it hunted,
and was hunted. It dreamed of shelter.
他梦见他的创造,亦梦见他毁灭。它梦见他在狩猎,亦梦见被猎捕。他梦见温馨的居所。
Hah, the original interface. A million years old, and it still works.But
what true structure did this player create, in the reality behind the screen?
哎,那原始的界面。经历百万年的岁月,它依然在工作。只是他在屏幕后的真实里,到底创造了什么真实的世界呢?
题目描述
C 国一共有 N 个村庄,N−1 条道路。这些道路都可以双向通行。保证小 S 可以从一座村庄到其他任何一座村庄。这 N 个村庄编号为 1 到 N。
刚开始小 S 对第 i 个村庄的好感值为 Ai。小 S 的假期一共有 M 天,他会在 C 国旅行一共 M 天。每一天他会选择来到当前好感值最高的村庄。如果有好感值相同的村庄,他会选择编号最小的村庄。假设这一天他来到村庄 X,那么这一天结束后,与村庄 X 直接相邻所有村庄的好感值都会增加 1。即能从 X 出发仅经过一条道路到达的村庄好感值会增加 1。因为小 S 已经在村庄 X 待过一天了,所以这一天结束后村庄 X 的好感值并不会增加。
现在小 S 想要知道经过 M 天的旅行后好感值最高的村庄。
如果有多个好感值最高的村庄,输出编号最小的。
输入格式
本题单个测试点包含多组测试数据。
第一行一个正整数 T 表示数据组数。
对于每组数据:
第一行包括两个正整数 N,M,表示村庄个数和旅行天数。
接下来一行 N 个整数,第 i 个整数表示第 i 座村庄的好感值 Ai。
接下来 N−1 行。每行两个整数 x,y 表示村庄 x 和村庄 y 之间有一条双向通行的道路。
输出格式
一个整数表示 M 天结束后好感值最高的村庄的编号。如果有多个好感值最高的村庄,输出编号最小的。
提示
样例说明
对于第一组数据,小 S 在 2 号村庄旅行了 3 天,结束时村庄 1,2 的好感值分别为 5,6。所以答案输出 2。
对于第二组数据,结束时三个村庄的好感值分别为 3,7,8,所以答案输出 3。
数据规模与约定
对于 100% 的数据,1≤N≤2×106,1≤M≤1018,1≤Ai≤231−1,1≤T≤10。
测试点编号 |
Ai≤ |
∑N≤ |
M≤ |
测试点分值 |
1 |
10 |
20 |
10 |
5 |
2 |
102 |
2×102 |
102 |
10 |
3 |
103 |
2×103 |
103 |
15 |
4 |
105 |
2×105 |
105 |
25 |
5 |
|
2×106 |
|
45 |
提示
本题输入量较大,请使用较快的读入方式。