思路:

不难看出, 对于某个点$i$, 后一次更新的值一定会覆盖前一次更新的值

我们给每个节点存储两个值key(k, v) 分别表示,更新的优先级和更新的值

最后, 我们从根节点开始, 遍历每一个子节点, 如果该子节点的优先级小于父节点的优先级, 则更新子节点的key为父节点的key

注意点 : 此题输入输出数据过大, 自己写快读, 开O2, 不然会超时

题目描述

小海棠得到了顶点个数为n的树，树的编号从1到n，每个节点都有一个命令编号(所有节点的命令编号初始为0)。 小海棠指定1为树的根，她每次将向某个节点发送命令X，节点在接到命令后将本节点的命令编号更新为x，并向自己所有子节点传播命令x，小海棠想直到在她执行完所有命令后每个节点的命令编号是多少。

输入描述

多组样例，第一行包含一个整数T表示样例组数。 每组样例第一行包含两个整数n,k 分别表示节点个数和指令的条数。 第二行包含$n-1$个整数，第$i$个整数表示节点$(i+1)$的父亲节点为$a_i$。 接下来k行每行包含两个整数x,y，表示对x节点执行指令y。

输出描述

每组样例输出一行用空格分离的n个整数，表示所有命令执行完成后的命令编号

样例

输入1

2
3 2
1 2
1 1895
2 129
4 1
1 1 1
3 1

输出1

1895 129 129
0 0 1 0

提示

$T <= 20$, $n,k <= 100000$, $1<=x<=100000$