先观察操作本质:
因此每次新赋的值都严格大于所有初始权值,而且也严格大于之前修改过的值。 所以每次在子树中找“当前权值最小的点”,就是在这个子树里找当前权值最小的位置,然后做一次单点修改。
给定一棵由 n 个节点(编号为1∼n)和n−1 条边构成的、根节点为 1 的树。
初始时,每个节点 i 的权值为 ai=i。
接下来共有m 次修改操作。第 j 次操作(j 从1开始)给出一个节点 x:
请输出所有节点在所有操作完成后的最终权值。
第一行输入两个整数 n 和m(2≤n,m≤105),分别表示树的节点数量和操作次数;
此后n−1 行,每行输入两个整数ui和vi(1≤ui,vi≤n;ui=vi),表示树上第i 条边;保证构成一棵以节点 1 为根的树;
随后 m行,每行输入一个整数x(1≤x≤n),表示第 j 次操作的节点编号。
在一行上输出n 个整数,分别表示节点 1到节点n的最终权值;整数之间用空格分隔
输入
3 2
1 2
1 3
1
2
输出
4 5 3
说明
在这个样例中: