← 返回题目列表

AtCoder · arc063_c

E. 树上的整数

中文机器翻译题面 查看原题

分数: 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

下图是高桥睡着时的树。对于每个顶点,其旁边写入的整数代表该顶点的索引,写入该顶点的整数是高桥写入的整数。

6da26f89839711a520acdf5c3e1cc309.png

例如,Aoki 可以通过将整数写入其余顶点来满足条件,如下所示:

1858d5af5a2c0e51aca39a39d765debb.png

这对应于示例输出 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.