P7043 "MCOI-03" Village Kingdom

$\texttt{What did this player dream?}$ What did he dream of? $\texttt{This player dreamed of sunlight and trees.Of fire and water.}$ He dreamed of sunlight and trees. He dreamed 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.}$ He dreamed of what he created, and he also dreamed of what he destroyed. It dreamed that it was hunting, and also being hunted. He dreamed of a warm 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?}$ Ah, the original interface. After a million years, it still works. But in the reality behind the screen, what real world did he actually create?

Country C has $N$ villages and $N-1$ roads. All roads can be traveled in both directions. It is guaranteed that Little S can reach any other village from any village. The $N$ villages are numbered from $1$ to $N$. At the beginning, Little S's favorability toward village $i$ is $A_i$. Little S has a $M$-day vacation, and he will travel in Country C for a total of $M$ days. Each day, he will choose to go to the village with the highest current favorability. If there are multiple villages with the same favorability, he will choose the one with the smallest index. Suppose that on this day he goes to village $X$. Then after this day ends, the favorability of all villages directly adjacent to village $X$ will increase by $1$. That is, the favorability of villages that can be reached from $X$ by traveling along exactly one road will increase by $1$. Since Little S has already stayed in village $X$ for one day, after this day ends, the favorability of village $X$ itself will not increase. Now Little S wants to know which village has the highest favorability after $M$ days of traveling. If there are multiple villages with the highest favorability, output the smallest index.

**This problem contains multiple testcases in a single test point.** The first line contains a positive integer $T$, representing the number of testcases. For each testcase: The first line contains two positive integers $N, M$, representing the number of villages and the number of travel days. The next line contains $N$ integers. The $i$-th integer represents the favorability $A_i$ of village $i$. The next $N-1$ lines each contain two integers $x, y$, indicating that there is a bidirectional road between village $x$ and village $y$.

Output one integer, representing the index of the village with the highest favorability after $M$ days. If there are multiple villages with the highest favorability, output the smallest index.

#### Sample Explanation For the first testcase, Little S traveled in village $2$ for $3$ days. At the end, the favorability of villages $1$ and $2$ are $5$ and $6$, respectively. Therefore the answer is $2$. For the second testcase, at the end, the favorability of the three villages are $3, 7, 8$, so the answer is $3$. #### Constraints For $100\%$ of the testdata, $1 \le N \le 2\times10^6$, $1 \le M \le 10^{18}$, $1 \le A_i \le 2^{31}-1$, $1 \le T \le 10$. | Test Point ID | $A_i \le$ | $\sum N \le$ | $M \le$ | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $\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$ | #### Note **The input size of this problem is large. Please use a fast input method.** Translated by ChatGPT 5