分数: 450 点
问题陈述
有 N+1 序列 A_0, A_1, \ldots, A_{N}. A_i 定义如下:
- A_0 是一个空序列。
- A_i\ (1\leq i\leq N) 是通过附加整数获得的序列 y_i 到序列末尾 A_{x_i}\ (0\leq x_i\lt i).
求排列 P=(P_1, P_2,\ldots,P_N) of (1,2,\ldots,N) 满足以下条件:
- 对于 i = 1,2,\ldots,N-1,以下条件之一成立:
- A_{P_i} 按字典顺序小于 A_{P_{i+1}}.
- A_{P_i}= A_{P_{i+1}} 和 P_i\lt P_{i+1}
换句话说,当 A_1,A_2,\ldots,A_N 按字典顺序排列(当有多个相等序列时,先排列索引较小的序列), P 是该排列中出现的索引序列。
序列的字典顺序是什么?
一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果满足以下两个条件之一。 在这里, |S| 和 |T| 代表的长度 S 和 T。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i (在数值上)小于 T_i.
约束
- 1\leq N\leq 3\times 10^5
- 0\leq x_i\lt i
- 1\leq y_i\leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 x_2 y_2 \vdots x_N y_N
输出
输出 P_1, P_2, \ldots, P_N 位于一行,以空格分隔。
示例输入 1
4 0 2 0 1 2 2 0 1
示例输出 1
2 4 3 1
A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1),所以 P=(2,4,3,1).
示例输入 2
5 0 1 0 1 0 1 0 1 0 1
示例输出 2
1 2 3 4 5
A_1 = A_2 = A_3 = A_4 = A_5 = (1).
示例输入 3
10 0 305186313 1 915059758 0 105282054 1 696409999 3 185928366 3 573289179 6 254538849 3 105282054 5 696409999 8 168629803
示例输出 3
3 8 10 5 9 6 7 1 4 2