题目背景

小 $Y$ 不喜欢 $toptree$ 。

题目描述

有一个 $n$ 个点的树 $T(r)=(V,E)$，其中 $V$ 为 $T$ 的点集， $E$ 为 $T$ 的边集，点的编号依次为 $1,2,3,4，……,n$，根节点为 $Root$ ，记 $x$ 节点的深度 $D(x)$ 表示节点 $x$ 到 $Root$ 的唯一简单路径的边的条数。

对于一个非空点集 $S\subseteq V$ ，我们可以对 $S$ 进行 任意次数 如下操作，称为拓展：

• 选择 $x\in S,y\in S$ ，然后把 $x$ 到 $y$ 的唯一简单路径上的所有点加入 $S$ 。

如果对于某一个由拓展得到的 $S'$，其无法再通过拓展得到别的点集，我们就称 $S'$ 是最初的点集 $S$ 的 完备邻域，记作 $N(S)=S'$ ，可证明 $N(S)$ 是存在且唯一的。

令 $R(S)$ 代表所有 $x\in N(S)$ 的 $x$ 中，$D(x)$ 最小的 $x$ 的编号。

现在给定一个排列 $p_1,p_2……,p_n$，请你对于 $Root=1\to n$，求出 :

$$\sum_{1\leq l\leq r\le n}R(\{p_l,p_{l+1}……p_{r-1},p_r\}) $$

输入格式

第一行一个正整数 $n$ 。

接下来 $n-1$ 行，每行两个整数 $x,y$，代表一条树上的边 $(x,y)\in E$ 。

接下来一个长度为 $n$ 的排列代表 $p_n$ 。

输出格式

一共 $n$ 个数，第 $i$ 个数代表 $Root=i$ 时的答案。

输入样例

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

输出样例

27
46
45
54
55

数据规模

• $15\%$，$1\leq n\leq 500$

• 另$15\%$，$1\leq n\leq 2000$

• 另$20\%$，$1\leq n\leq 9000$

• 另$20\%$，$x_i=i,y_i=i+1$

• 另$20\%$ $1\leq n\leq 1\times 10^5$

$100\%$ ，$1\leq n\leq 3\times 10^5$ 。

弹跳(jump)