問題
背景
鳗鱼王国有许多城镇,这些城镇之间存在支配关系,并且已知这种关系呈树状结构。每个城镇都希望与某个其他城镇建立友好关系,但如果城镇之间存在支配关系,则不能建立友好关系。此外,每个城镇都希望与人口尽可能接近的城镇建立友好关系。我们来考虑每个城镇应该与哪个城镇建立友好关系。
課題
当给出一个带有顶点值的有根树时,对于每个顶点,回答在既不是其子孙也不是其祖先的顶点中,其值最接近该顶点值的顶点的值。
如果有多个顶点拥有最接近的值,回答其中值最小的顶点的值。另外,对于没有既不是其子孙也不是其祖先的顶点的顶点 -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