P16072 [ICPC 2023 NAC] Fail Fast

一个大型软件项目编写了许多自动化测试来帮助保证质量。当源代码发生变更时，所有自动化测试会按某种顺序执行，以帮助证明代码变更没有破坏某些已有的功能。当且仅当所有自动化测试都通过时，代码变更才被接受。 运行所有这些自动化测试的成本很高，因此一旦出现一个失败，剩余的测试就不会再运行。每个测试的执行需要一定的 CPU 时间。当测试序列中出现失败时，运行该序列的成本是执行到并包括失败测试为止的所有测试的 CPU 时间之和。如果所有测试都通过，则运行该序列的成本为 $0$。 某个自动化测试可能依赖于另一个自动化测试的输出。例如，自动化测试 **A** 可能依赖于自动化测试 **B** 的输出。在这种情况下，测试 **B** 必须在测试 **A** 之前执行。注意，测试 **B** 和测试 **A** 之间可以运行其他测试。 根据对历史数据的分析和代码变更的评估，每个自动化测试都有一个已知的通过概率。任意给定测试的通过概率与其他测试的通过概率相互独立。 给定执行每个测试所需的 CPU 时间、每个测试的失败概率以及依赖关系，请确定一个顺序依次执行这些测试，以最小化运行该测试序列的期望成本。

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示自动化测试的数量。 接下来的 $n$ 行，每行包含三个值：整数 $c$（$1 \le c \le 10^6$）、实数 $p$（$0 < p < 1$）和整数 $d$（$0 \le d \le n$），其中 $c$ 是运行该自动化测试所需的 CPU 时间，$p$ 是该测试通过的概率，$d$ 是该测试所依赖的测试的索引，如果该测试没有依赖，则 $d = 0$。测试的索引按照输入顺序从 $1$ 到 $n$ 编号。 每个概率最多保留六位小数。依赖关系图中不存在循环依赖。

输出 $n$ 行，每行一个整数，按顺序给出要运行的测试的索引。该顺序必须使得运行测试的期望成本与最优顺序的期望成本之间的绝对误差或相对误差不超过 $10^{-6}$。任何满足此约束的顺序都将被接受。

翻译由 DeepSeek V3.2 完成