「MCOI-03」村国

$\texttt{What did this player dream?}$ 他梦见了什么？ $\texttt{This player dreamed of sunlight and trees.Of fire and water.}$ 他梦见了阳光与树木。梦见了火与水。 $\texttt{It dreamed it created. And it dreamed it destroyed. It dreamed it hunted,}$ $\texttt{and was hunted. It dreamed of shelter.}$ 他梦见他的创造，亦梦见他毁灭。它梦见他在狩猎，亦梦见被猎捕。他梦见温馨的居所。 $\texttt{Hah, the original interface. A million years old, and it still works.But}$ $\texttt{ what true structure did this player create, in the reality behind the screen?}$ 哎，那原始的界面。经历百万年的岁月，它依然在工作。只是他在屏幕后的真实里，到底创造了什么真实的世界呢？

C 国一共有 $N$ 个村庄，$N-1$ 条道路。这些道路都可以双向通行。保证小 S 可以从一座村庄到其他任何一座村庄。这 $N$ 个村庄编号为 $1$ 到 $N$。 刚开始小 S 对第 $i$ 个村庄的好感值为 $A_i$。小 S 的假期一共有 $M$ 天，他会在 C 国旅行一共 $M$ 天。每一天他会选择来到当前好感值最高的村庄。如果有好感值相同的村庄，他会选择编号最小的村庄。假设这一天他来到村庄 $X$，那么这一天结束后，与村庄 $X$ 直接相邻所有村庄的好感值都会增加 $1$。即能从 $X$ 出发仅经过一条道路到达的村庄好感值会增加 $1$。因为小 S 已经在村庄 $X$ 待过一天了，所以这一天结束后村庄 $X$ 的好感值并不会增加。 现在小 S 想要知道经过 $M$ 天的旅行后好感值最高的村庄。 如果有多个好感值最高的村庄，输出编号最小的。

**本题单个测试点包含多组测试数据**。 第一行一个正整数 $T$ 表示数据组数。 对于每组数据： 第一行包括两个正整数 $N,M$，表示村庄个数和旅行天数。 接下来一行 $N$ 个整数，第 $i$ 个整数表示第 $i$ 座村庄的好感值 $A_i$。 接下来 $N-1$ 行。每行两个整数 $x,y$ 表示村庄 $x$ 和村庄 $y$ 之间有一条双向通行的道路。

一个整数表示 $M$ 天结束后好感值最高的村庄的编号。如果有多个好感值最高的村庄，输出编号最小的。

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

2
3

#### 样例说明 对于第一组数据，小 S 在 $2$ 号村庄旅行了 $3$ 天，结束时村庄 $1,2$ 的好感值分别为 $5,6$。所以答案输出 $2$。 对于第二组数据，结束时三个村庄的好感值分别为 $3,7,8$，所以答案输出 $3$。 #### 数据规模与约定 对于 $100\%$ 的数据，$1 \le N\le 2\times10^6$，$1 \le M\le10^{18}$，$1 \le A_i\le2^{31}-1$，$1 \le T\le10$。 | 测试点编号 | $A_i\le$ | $\sum N \le$ | $M \le $ | 测试点分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $\rm 1$ | $10$ | $20$ | $10$ | $5$ | | $\rm 2$ | $10^2$ | $2 \times 10^2$ | $10^2$ | $10$ | | $\rm 3$ | $10^3$ | $2 \times 10^3$ | $10^3$ | $15$ | | $\rm 4$ | $10^5$ | $2 \times 10^5$ | $10^5$ | $25$ | | $\rm 5$ | | $2 \times 10^6$ | | $45$ | #### 提示 **本题输入量较大，请使用较快的读入方式。**