解题思路

先观察操作本质：

• 初始时每个点 $i$ 的权值为 $a_i=i$。
• 第 $j$ 次操作会把某个点的权值改成 $n+j$。

因此每次新赋的值都严格大于所有初始权值，而且也严格大于之前修改过的值。 所以每次在子树中找“当前权值最小的点”，就是在这个子树里找当前权值最小的位置，然后做一次单点修改。

题目内容

给定一棵由 $n$ 个节点（编号为$1$∼$n$）和$n−1$ 条边构成的、根节点为 $1$ 的树。

初始时，每个节点 i 的权值为 $a_i=i$。

接下来共有$m$ 次修改操作。第 $j$ 次操作（$j$ 从$1$开始）给出一个节点 $x$：

• 找出以 $x$ 为根的子树中当前权值最小的节点，并将该节点的权值修改为$j+n$。

请输出所有节点在所有操作完成后的最终权值。

输入描述

第一行输入两个整数 $n$ 和$m(2≤n,m≤10^5)$，分别表示树的节点数量和操作次数；

此后$n−1$ 行，每行输入两个整数$u_i$和$v_i(1≤u_i,v_i≤n;u_i≠v_i)$，表示树上第$i$ 条边；保证构成一棵以节点 $1$ 为根的树；

随后 $m$行，每行输入一个整数$x(1≤x≤n)$，表示第 $j$ 次操作的节点编号。

输出描述

在一行上输出$n$ 个整数，分别表示节点 $1$到节点$n$的最终权值；整数之间用空格分隔

样例1

输入

3 2
1 2
1 3
1 
2

输出

4 5 3

说明

在这个样例中：

• 初始时$a=${$1,2,3$}；
• 第 $1$次操作$x=1$，子树为所有节点，最小权值节点为 $1$，更新其权值为 $1+3=4$；
• 第 $2$ 次操作 $x=2$，子树仅含节点 $2$，更新其权值为$2+3=5$；
• 最终权值为 {$4,5,3$}。