← 返回题目列表

AtCoder · agc010_f

F. 树游戏

中文机器翻译题面 查看原题

分数: 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


请注意,正确的输出可能是空行。