题目内容

在一家大型公司中，员工构成一棵以高管 $1$ 为根的树形组织架构，编号为 $1$ 到 $n$。每位员工 $i$ 拥有一个能力值 $a_i$。

对于任意非根员工 $i\ (i > 1)$，他会沿着组织树从 $i$ 向上级路径追溯，找到离他最近、且能力值严格大于 $a_i$ 的第一个上级 $j$。如果这样的 $j$ 存在，则在 $i$ 与 $j$ 之间建立一条额外的直接沟通渠道（无向边）；否则，不建立额外渠道。

在所有额外渠道添加完毕后，定义每个员工 $i$ 到高管 $1$ 的互通距离为最少的边数。你需要计算并输出每个员工的最终互通距离。

【名词解释】

• 上级：以 $1$ 为根的树中，若节点 $x$ 位于 $1$ 到 $y$ 的简单路径上且 $x eq y$，则称 $x$ 是 $y$ 的上级。根节点 $1$ 没有上级。
• 能力值严格大于：指在数值上完全大于，不允许等于。

【数据范围】

• 员工数量 $n$ 满足 $1 \le n \le 2 imes 10^5$。
• 能力值范围：$1 \le a_i \le 10^{11}$。
• 给出的 $n-1$ 条边构成一棵以 $1$ 为根的合法树。

输入描述

输入通过标准输入提供，格式如下：

第一行：一个整数 $n$，表示员工数量。 第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$，依次表示每位员工的能力值。 接下来的 $n-1$ 行：每行两个整数 $u$ 和 $v$，表示 $u$ 与 $v$ 之间存在直接上下级关系。

输出描述

输出一行，包含 $n$ 个整数 $d_1, d_2, \dots, d_n$，用空格分隔，其中 $d_i$ 表示在所有额外渠道添加后，员工 $i$ 到高管 $1$ 的最短互通距离（以边数计）。

样例1

输入

4
10 5 6 7
1 2
2 3
3 4

输出

0 1 1 1

说明

员工 2 能力值为 5，上级 1 能力值 10 严格大于 5，因此建立额外渠道 2-1（已存在）。员工 3 能力值为 6，向上追溯：父节点 2 能力值 5 不大于 6，祖父节点 1 能力值 10 大于 6，最近满足条件的上级为 1，因此建立额外渠道 3-1，将 3 到 1 的距离缩短为 1。同理，员工 4 能力值为 7，父节点 3（能力 6）和祖父 2（能力 5）均不大于 7，曾祖父 1（能力 10）大于 7，建立额外渠道 4-1，距离变为 1。最终互通距离：$d_1=0$，$d_2=1$，$d_3=1$，$d_4=1$。

样例2

输入

5
5 3 4 2 6
1 2
2 3
3 4
1 5

输出

0 1 1 2 1

说明

员工能力值分别为 $a_1=5$，$a_2=3$，$a_3=4$，$a_4=2$，$a_5=6$。组织树：1-2-3-4 链，1-5 分支。 对于员工 2（能力 3），最近严格更大上级为 1（能力 5），建立 2-1。 员工 3（能力 4），路径 3-2-1：2 能力 3 不大于 4，1 能力 5 大于 4，建立额外渠道 3-1，距离 1。 员工 4（能力 2），路径 4-3-2-1：最近满足 $>2$ 的上级为 3（能力 4），加边 4-3（原树已有），距离经 3-1 缩短为 4-3-1，共 2 条边。 员工 5（能力 6），上级 1 能力 5 不大于 6，无额外渠道，距离 1。 最终距离：0 1 1 2 1。

样例3

输入

1
10

输出

0

说明

只有一名员工，即高管本人，无需额外渠道，到自身的距离为 0。

样例4

输入

6
100 10 20 30 5 40
1 2
2 4
4 6
1 3
3 5

输出

0 1 1 1 2 1

说明

组织树：1 有两个子节点 2 和 3；2 下接 4 再下接 6；3 下接 5。能力值依次为 $100, 10, 20, 30, 5, 40$。 员工 2（能力 10）和 3（能力 20）的直接上级 1 能力 100 均大于他们，建立边 2-1、3-1（原本已有），距离为 1。 员工 4（能力 30）路径 4-2-1：2 能力 10 不大于 30，1 能力 100 大于 30，建立额外渠道 4-1，距离为 1。 员工 6（能力 40）路径 6-4-2-1：所有上级中只有 1 的能力 100 > 40，建立 6-1，距离为 1。 员工 5（能力 5）路径 5-3-1：3 能力 20 > 5，最近更大上级为 3，建立 5-3（原本已有），距离则为 5-3-1 共 2 条边。 最终结果：0 1 1 1 2 1。