分数: 800 点
问题陈述
我们有一棵树 N 顶点。顶点已编号 1, 2, ..., N。的 i-th (1 ≦ i ≦ N - 1) 边连接两个顶点 A_i 和 B_i.
Takahashi 将整数写入 顶点的 K 。具体来说,对于每个 1 ≦ j ≦ K,他写下了整数 P_j 进入顶点 V_j。其余顶点留空。之后,他累了,就睡着了。
然后,青木出现了。他试图通过将整数写入所有空顶点来满足以下条件,从而让高桥感到惊讶:
- 条件:对于有边直接相连的任意两个顶点,写入这两个顶点的整数相差正好 1.
确定是否可以将整数写入所有空顶点,从而满足条件。如果答案是肯定的,请找到一种满足条件的特定方法。
约束
- 1 ≦ N ≦ 10^5
- 1 ≦ K ≦ N
- 1 ≦ A_i, B_i ≦ N (1 ≦ i ≦ N - 1)
- 1 ≦ V_j ≦ N (1 ≦ j ≦ K)(21:18,此约束中的错误已更正)
- 0 ≦ P_j ≦ 10^5 (1 ≦ j ≦ K)
- 给定的图是一棵树。
- 全部 v_j 是不同的。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
K
V_1 P_1
V_2 P_2
:
V_K P_K
输出
如果可以将整数写入所有空顶点从而满足条件,则打印 Yes。否则,打印 No.
如果可以满足条件,则打印 另外 N 行。 v-th (1 ≦ v ≦ N)其中 N 行应包含应写入顶点的整数 v。如果有多种方法可以满足条件,则接受其中任何一种。
示例输入 1
5 1 2 3 1 4 3 3 5 2 2 6 5 7
示例输出 1
Yes 5 6 6 5 7
下图是高桥睡着时的树。对于每个顶点,其旁边写入的整数代表该顶点的索引,写入该顶点的整数是高桥写入的整数。
例如,Aoki 可以通过将整数写入其余顶点来满足条件,如下所示:
这对应于示例输出 1。请注意,满足条件的其他输出也将被接受,例如:
Yes 7 6 8 7 7
示例输入 2
5 1 2 3 1 4 3 3 5 3 2 6 4 3 5 7
示例输出 2
No
示例输入 3
4 1 2 2 3 3 4 1 1 0
示例输出 3
Yes 0 -1 -2 -3
Aoki 写入的整数可能为负数或超过 10^6.