作者:MCOI
题目描述
因为上传者造数据非常辛苦
所以没有造原作者的那样的超大数据
数据很水,但是保证:一定拥有原作者的毒瘤数据
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天结束后好感值最高的村庄的编号。如果有多个好感值最高的村庄,输出编号最小的。