← 返回题目列表

AtCoder · utpc2013_09

I. 统治与友谊

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

問題

背景

鳗鱼王国有许多城镇,这些城镇之间存在支配关系,并且已知这种关系呈树状结构。每个城镇都希望与某个其他城镇建立友好关系,但如果城镇之间存在支配关系,则不能建立友好关系。此外,每个城镇都希望与人口尽可能接近的城镇建立友好关系。我们来考虑每个城镇应该与哪个城镇建立友好关系。

課題

当给出一个带有顶点值的有根树时,对于每个顶点,回答在既不是其子孙也不是其祖先的顶点中,其值最接近该顶点值的顶点的值。

如果有多个顶点拥有最接近的值,回答其中值最小的顶点的值。另外,对于没有既不是其子孙也不是其祖先的顶点的顶点 -1 。

配点

200

入力

输入按以下格式给出。

N
a1
...
aN
s1 t1
...
sN-1 tN-1

N 是顶点的数量,ai 是 您也可以写 i 第n个顶点所持有的值,si 和 按字典顺序比较 ti 是 您也可以写 ti 是 在 si 表示它是某顶点的孩子。

制約

输入中的每个变量都满足以下约束。

  • 1 \leq N \leq 105
  • 1 \leq ai \leq 109
  • 0 \leq si, ti \lt N

保证该图是一个有根树。

出力

输出是 由 N 行组成。 i(1 \leq i \leq N) 在线 i 在第n个顶点既不是其子孙也不是其祖先的顶点中,输出其值最接近该顶点值的顶点的值。但对于没有既不是其子孙也不是其祖先的顶点的顶点 -1 。

入力例1

7
1
2
3
4
5
6
7
0 1
1 2
1 3
0 4
4 5
4 6
図 1:输入示例1所表示的支配关系

输入示例 1 的输出示例 路径

-1
5
4
3
4
7
6

显示每个顶点既不是其子孙也不是其祖先的顶点可能的一种情况。例如顶点1的后代也不是其祖先的顶点是4,5,6,顶点2的后代也不是其祖先的顶点是3,4,5,6。

図 2: 頂点1的子孙也不是祖先的顶点
図 3: 頂点2的子孙也不是祖先的顶点

入力例2

4
1
2
3
4
0 1
1 2
2 3

输入示例 2 的输出示例

-1
-1
-1
-1

,所有顶点中不存在既不是其子孙也不是其祖先的顶点。

入力例3

5
1
1
2
3
4
0 1
0 2
0 3
0 4

输入示例 3 的输出示例

-1
2
1
2
3