AT_scpc2026_div2_k.Cosmic Playground

While exploring the galaxy, Navi and Hyeongtae discovered a cosmic playground! The cosmic playground consists of $N$ points and $N-1$ bidirectional passages. Each point in the cosmic playground is numbered from $1$ to $N$. The $i$th passage connects points $u_i$ and $v_i$ in both directions. It is always possible to travel between any two distinct points using only the passages. In other words, the cosmic playground has a tree structure.

Each point is connected to a single slide. For a permutation $P=[P_1, P_2, \dots, P_N]$ of length $N$, sliding down the slide at point $i$ moves you to point $P_i$.

Navi wants to slide down the slides non-stop to enjoy the thrill of speed. On the other hand, Hyeongtae is worried that if Navi travels too far, Navi might get lost in space. After much deliberation, Navi and Hyeongtae defined the risk level $f(r)$ of point $r$ as follows:

• The distance between points $a$ and $b$ is the minimum number of passages one must traverse to reach point $b$ from point $a$ using only the passages.
• Navi starts at point $s$ and continues moving using only slides, while Hyeongtae watches Navi from point $r$. The maximum distance between point $r$ and any point Navi can reach is defined as the maximum distance $d(r, s)$.
• The risk level $f(r)$ when Hyeongtae remains at point $r$ is the sum of the maximum distances $\sum\limits_{s = 1}^{N}{d(r, s)}$ when Navi starts from each point.

Hyeongtae wants to stay at the point where the risk level is minimized. Let us help Hyeongtae by calculating the risk level for each point.

What is a permutation? A permutation of length $N$ is a sequence that contains exactly one of each integer from $1$ to $N$. For example, $[2,1,4,3]$ is a permutation, but $[4, 2, 1, 1]$ and $[1, 2, 3, 5]$ are not.

在探索银河系的过程中，Navi 和 Hyeongtae 发现了一座宇宙游乐场！该宇宙游乐场由 $N$ 个点和 $N-1$ 条双向通道组成。游乐场中的每个点均编号为 $1$ 至 $N$。第 $i$ 条通道双向连接点 $u_i$ 和 $v_i$。任意两个不同点之间总能仅通过这些通道相互到达。换言之，该宇宙游乐场具有树形结构。

每个点都连接着一条滑梯。对于一个长度为 $N$ 的排列 $P=[P_1, P_2, \dots, P_N]$，从点 $i$ 滑下滑梯将把你传送至点 $P_i$。

Navi 想要不停歇地滑下滑梯，以体验速度带来的刺激感。而 Hyeongtae 则担心：若 Navi 行进距离过远，可能会在太空中迷路。经过反复商议，Navi 和 Hyeongtae 定义了点 $r$ 的风险等级 $f(r)$ 如下：

• 点 $a$ 与点 $b$ 之间的距离定义为：仅使用通道从点 $a$ 到达点 $b$ 所需经过的最少通道数。
• Navi 从点 $s$ 出发，仅通过滑梯持续移动；Hyeongtae 则在点 $r$ 处观察 Navi。Navi 可达的所有点中，与点 $r$ 距离最大的那个距离，称为最大距离 $d(r, s)$。
• 当 Hyeongtae 停留在点 $r$ 时，其风险等级 $f(r)$ 定义为：当 Navi 分别从每个起点 $s = 1, 2, \dots, N$ 出发时，对应的最大距离 $d(r, s)$ 的总和，即 $\sum\limits_{s = 1}^{N}{d(r, s)}$。

Hyeongtae 希望停留在风险等级最小的那个点上。请帮助 Hyeongtae 计算每个点的风险等级。

什么是排列？一个长度为 $N$ 的排列是指恰好包含 $1$ 至 $N$ 中每个整数各一次的序列。例如，$[2,1,4,3]$ 是一个排列，但 $[4, 2, 1, 1]$ 和 $[1, 2, 3, 5]$ 不是。

The input is given from Standard Input in the following format:

$N$
$P_1$ $P_2$ $\dots$ $P_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输入从标准输入中按以下格式给出：

$N$
$P_1$ $P_2$ $\dots$ $P_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

Output $N$ integers $f(1), f(2), \dots, f(N)$, separated by spaces, where each integer represents the risk level of each point.

输出 $N$ 个整数 $f(1), f(2), \dots, f(N)$，以空格分隔，其中每个整数表示对应点的风险等级。

表示言語

/ /

Constraints

• $3 \le N \le 100\,000$
• $1 \le u_i < v_i \le N$
• The given graph is a tree.
• $P$ is a permutation.
• All input values are integers.

表示语言

/ /

限制条件

• $3 \le N \le 100\,000$
• $1 \le u_i < v_i \le N$
• 给定的图是一棵树。
• $P$ 是一个排列。
• 所有输入值均为整数。