← 返回题目列表

Codeforces · 1286/B

B. 树上的数字

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

Evlampiy 被赐予了一棵有根的树。树的顶点编号从 $$$1$$$ 到 $$$n$$$。它的每个顶点上还写有一个整数$$$a_i$$$。对于每个顶点 $$$i$$$,Evlampiy 计算 $$$c_i$$$ — 顶点 $$$i$$$ 子树中的顶点数 $$$j$$$,使得 $$$a_j < a_i$$$。

第二个例子的说明,第一个整数是$$$a_i$$$,括号中的整数是$$$c_i$$$

新年过后,Evlampiy 不记得他的礼物是什么了!他记得树和 $$$c_i$$$ 的值,但他完全忘记了顶点上写了哪些整数 $$$a_i$$$。

帮助他恢复初始整数!

输入

第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 2000)$$$ — 树中的顶点数。

接下来的 $$$n$$$ 行包含顶点的描述:第 $$$i$$$ 行包含两个整数 $$$p_i$$$ 和 $$$c_i$$$ ($$$0 \leq p_i \leq n$$$; $$$0 \leq c_i \leq n-1$$$),其中 $$$p_i$$$ 是父级顶点 $$$i$$$ 或 $$$0$$$(如果顶点 $$$i$$$ 是根,并且 $$$c_i$$$ 是顶点 $$$i$$$ 的子树中的顶点 $$$j$$$ 的数量,使得 $$$a_j < a_i$$$。

保证 $$$p_i$$$ 的值描述具有 $$$n$$$ 个顶点的有根树。

输出

如果存在解,则在第一行打印“YES”,在第二行输出 $$$n$$$ 整数 $$$a_i$$$ $$$(1 \leq a_i \leq {10}^{9})$$$。如果有多个解,输出任意一个。可以证明,如果有解,那么也存在所有$$$a_i$$$都在$$$1$$$和$$$10^9$$$之间的解。

如果没有解决方案,则打印“NO”。

示例

输入 #1

3
2 0
0 2
2 0

输出 #1

YES
1 2 1

输入 #2

5
0 1
1 3
2 1
3 0
2 0

输出 #2

YES
2 3 2 1 2