解题思路

先把原图看成一棵以 $1$ 为根的树。

对于每个节点 $i$ （ $i > 1$ ），题目要求找到：

题目内容

给定一棵以根节点 $1$ 为根的无向树，节点编号为 $1,2,...,n$ ，每个节点 $i$ 的权值为 $x_i$ 。对于每个节点 $i(i>1)$ :

在加入所有额外边之后，计算每个节点到根节点 $1$ 的最短距离(以边数计)。

【名词解释】

祖先节点：在一棵以 $u$ 为根的树中，若点 $x$ 在 $u$ 到 $v$ 的简单路径上，且 $x≠v$ ，则称 $x$ 是 $v$ 的祖先节点。根节点没有祖先节点。

第一行输入整数 $n(1≤n≤2×10^5)$ ，表示节点数量；

第二行输入 $n$ 个整数 $x_1，x_2,...,x_n(1≤x_i≤10^{11})$ ，表示各节点权值；

接下来 $n-1$ 行，每行输入两个整数

在同一行输出 $n$ 个整数 $d_1，d_2，...，d_n$ 以空格分隔，其中 $d_i$ 表示在加入额外边之后，节点 $i$ 到根节点 $1$ 的最短距离，

在几乎全部的情况下， $PyPy$ 的运行速度优于 $Python$ ，我们建议您选择对应版本的 $PyPy$ 进行提交、而不是 $Python$ 。

输入

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

输出

0 1 1 1 1 1 1

说明

原树是一条链： $1-2-3-4-5-6-7$ ，各点权值为 $[7,1,2,3,4,5,6]$ 。

对于每个节点 $i>1$ ，沿原树从 $i$ 到 $1$ 的路径，找到第一个权值严格大于 $x_i$ 的祖先并添加额外边:

添加所有额外边后，节点 $2,...,7$ 均可通过新边直接到达根 $1$ ，距离均为 $1$ ；根节点 $1$ 距离为 $0$ 。

输入

输出

0 1 1 1 2