[R65D]构造树 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个编号为 $1$ 到 $n$ 的点。你需要构造一棵有根树。

对于每个点 $i$，给定两个整数：

• $d_i$：点 $i$ 在树中的深度（根节点的深度为 $0$）；
• $c_i$：点 $i$ 最多可以拥有的儿子数量。

对于任意非根节点 $i$，其父亲的编号是 $p_i$。

在所有合法的构造中，你需要使父亲数组 $p_1, p_2, \dots, p_n$ 的字典序最小（其中根节点的父亲记为 $0$）。

保证存在至少一种合法的构造方法。

格式

输入格式

第一行输入一个正整数 $n$。

接下来 $n$ 行，每行输入两个非负整数 $d_i$ 和 $c_i$，表示第 $i$ 个点的深度和最大儿子数量。

输出格式

输出一行 $n$ 个整数 $p_1, p_2, \dots, p_n$，中间用单个空格隔开，表示字典序最小的合法父亲数组。

样例

样例输入 #1

6
0 3
1 2
1 0
2 0
2 0
1 1

样例输出 #1

0 1 1 2 2 1

样例解释 #1

各个点的深度和最大儿子数如下：

• 点 $1$：深度 $0$，最大儿子数 $3$
• 点 $2$：深度 $1$，最大儿子数 $2$
• 点 $3$：深度 $1$，最大儿子数 $0$
• 点 $4$：深度 $2$，最大儿子数 $0$
• 点 $5$：深度 $2$，最大儿子数 $0$
• 点 $6$：深度 $1$，最大儿子数 $1$

构造出的树结构为：

• $1$ 为根节点，$p_1 = 0$。
• 深度为 $1$ 的点 $2, 3, 6$ 的父亲均为 $1$（即 $p_2 = 1, p_3 = 1, p_6 = 1$）。点 $1$ 的实际儿子数量为 $3 \le 3$。
• 深度为 $2$ 的点 $4, 5$ 的父亲均为 $2$（即 $p_4 = 2, p_5 = 2$）。点 $2$ 的实际儿子数量为 $2 \le 2$。

最终的父亲数组为 0 1 1 2 2 1，这是所有合法构造中字典序最小的。

样例输入 #2

3
0 1
1 1
2 0

样例输出 #2

0 1 2

样例解释 #2

深度关系为 $1$（深度 0） $\to 2$（深度 1） $\to 3$（深度 2）。 对应的父亲数组为 0 1 2。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$2000$
$2$	$80$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le d_i \le n - 1$，$0 \le c_i \le n$。