UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2799. [Poi2012]Salaries

统计 下载数据

Description


给出一棵n个结点的有根树,结点用正整数1~n编号。
每个结点有一个1~n的正整数权值,不同结点的权值不相同,
并且一个结点的权值一定比它父结点的权值大(根结点的权值最大,一定是n)。
现在有些结点的权值是已知的,并且如果一个结点的权值已知,它父结点的权值也一定已知。
问还有哪些结点的权值能够唯一确定。

Input


第一行一个正整数n (n<=1,000,000),表示树的结点数。
下面共n行,第i行描述编号为i的结点,每行两个整数pi,zi (1<=pi<=n, 0<=zi<=n)。
pi表示结点i的父结点,如果i=pi,说明i是根结点。
当zi>0时,表示结点i的权值已知,并且就是zi;当zi=0时,表示结点i的权值未知。
测试数据保证满足题意,并且存在合法的方案。

Output

输出共n行,依次描述每个结点。如果结点i的权值能够唯一确定,第i行输出结点i的权值,否则第i行输出0。

Sample Input

10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0

Sample Output

2
2
10
1
9
5
8
0
0
0
0

Hint

Source

鸣谢Oimaster