分数: 1600 点
问题陈述
有一棵树 N 顶点,编号 1 通过 N。 的 i- 第 N-1 边连接顶点 a_i 和 b_i.
目前,有 A_i 石头放置在顶点 i。 高桥和青木将使用这棵树玩游戏。
首先,高桥将选择一个顶点并在其上放置一个棋子。 然后,从高桥开始,他们会交替执行以下操作:
- 从该棋子当前占据的顶点移除一颗棋子。
- 然后,将棋子移动到与当前占用的顶点相邻的顶点。
棋子占据的顶点上没有棋子而无法执行操作的玩家输掉游戏。 找到所有的顶点 v 这样高桥就可以把棋子放在 v 一开始就赢得了比赛。
约束
- 2 ≦ N ≦ 3000
- 1 ≦ a_i,b_i ≦ N
- 0 ≦ A_i ≦ 10^9
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
打印顶点的索引 v 这样高桥就可以把棋子放在 v 开头并赢得比赛,排成一行,按升序排列。
示例输入 1
3 1 2 3 1 2 2 3
示例输出 1
2
以下是高桥将棋子放在顶点时游戏的一种可能进展 2:
- 高桥将棋子移动到顶点 1。现在每个顶点上的石头数量为: (1,1,3).
- 青木将棋子移动到顶点 2。现在每个顶点上的石头数量为: (0,1,3).
- 高桥将棋子移动到顶点 1。现在每个顶点上的石头数量为: (0,0,3).
- 青木无法从顶点拿走棋子,因此高桥获胜。
示例输入 2
5 5 4 1 2 3 1 2 1 3 2 4 2 5
示例输出 2
1 2
示例输入 3
3 1 1 1 1 2 2 3
示例输出 3
请注意,正确的输出可能是空行。