[ARC063E] 木と整数
题意翻译
有一个$N$个点的树。顶点编号为$1$到$N$。
███(数据已删除)为$K$个点赋上了值,其余点不定
然后,██(数据已删除)出现了。他企图通过为所有未赋值顶点赋值来震慑███(数据已删除),条件如下:
* 对于任何由一条边直接连接的两个顶点,这两点点权恰好相差$1$
确定是否有合法方案。如果有,给出一个方案
题目描述
[problemUrl]: https://atcoder.jp/contests/arc063/tasks/arc063_c
$ N $ 頂点の木があり、頂点には $ 1,\ 2,\ ...,\ N $ と番号が振られています。$ i $ ($ 1\ ≦\ i\ ≦\ N\ -\ 1 $) 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。
高橋君は木の $ K $ 個の頂点に整数を書き込みました。具体的には、各 $ 1\ ≦\ j\ ≦\ K $ について、頂点 $ V_j $ に整数 $ P_j $ を書き込みました。その後、高橋君は居眠りを始めました。
木を見つけた青木君は、残りのすべての頂点に整数を書き込み、高橋君を驚かせようとしています。高橋君を驚かせるためには、木が次の条件を満たさなければなりません。
- 条件: 辺で直接結ばれた $ 2 $ つの頂点に書かれている整数の差がちょうど $ 1 $ である。
残りのすべての頂点に書き込む整数を工夫することで、木が条件を満たすようにできるか判定してください。もし可能な場合は、どのように整数を書き込めばよいかを具体的にひとつ求めて下さい。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ 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 $ ($ 1\ ≦\ v\ ≦\ N $) 行目には、頂点 $ v $ に書かれる整数を出力せよ。条件を満たすような整数の書き込み方が複数ある場合、そのうちいずれかひとつを出力すればよい。
输入输出样例
输入样例 #1
5
1 2
3 1
4 3
3 5
2
2 6
5 7
输出样例 #1
Yes
5
6
6
5
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
说明
### 制約
- $ 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^6 $ ($ 1\ ≦\ j\ ≦\ K $)
- 与えられるグラフは木になることが保証される
- $ V_j $ はすべて相異なる
### Sample Explanation 1
はじめ、木は以下の図のような状態である。頂点のそばに書かれた数が頂点番号を、頂点の中に書かれた青い数が元から書き込まれていた整数を表す。 !\[6da26f89839711a520acdf5c3e1cc309.png\](https://atcoder.jp/img/arc063/6da26f89839711a520acdf5c3e1cc309.png) 青木君はたとえば次のように残りの頂点に整数を書き込むことで木が条件を満たすようにできる。これは出力例 $ 1 $ に対応している。 !\[1858d5af5a2c0e51aca39a39d765debb.png\](https://atcoder.jp/img/arc063/1858d5af5a2c0e51aca39a39d765debb.png) 木が条件を満たしていれば、これとは異なった出力でも AC となることに注意せよ。たとえば、入力例 $ 1 $ に対しては ``` Yes 7 6 8 7 7 ``` という出力でも正答となる。
### Sample Explanation 3
新たに書き込む整数は負になったり $ 10^6 $ を超えたりしても構わない。