← 返回题目列表

AtCoder · code_thanks_festival_2018_f

F. 树上的硬币

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

配点 : 400 点

問題文

高桥先生,N 在由顶点组成的有根树上, 使用M 硬币可以执行以下操作: 您正在尝试执行 K 次。

这棵树有顶点 i 的父级是 p_i 。p_i = 0 的顶点是根。

对于每个操作,

  • 如果根上没有放置硬币,则在根上放置一枚新硬币

或

  • 放置硬币的顶点 1 选择一个并将硬币移给任何没有硬币的孩子。 您可以

。 经过

K 操作后, 所有M硬币必须放置在树上的某个地方。

1 第二枚硬币放在根上, 2 第二枚硬币放在根上,..., M 选择放置在根部的硬币所在的顶点。 v_1, v_2, ..., v_M 。

高桥君这一排 我想知道 v_1, v_2, ..., v_M 中哪一个按字典顺序最小。

请向高桥君询问此线路。

列 u_1, u_2, ..., u_M 是一列 按字典顺序小于 v_1, v_2, ..., v_M 意味着u_i < v_i 和所有 j < i 我们知道 u_j = v_j 成立。 1 \leq i \leq M 存在。

然而,只是 K 如果您无法执行以下操作, 如果您无法将M 硬币放在树上,-1 输出。

制約

  • 1 \leq M \leq N \leq 300
  • 0 \leq K \leq 10^5
  • 0 \leq p_i \leq N
  • p_i = 0 变为 只有一个 i 只是 1 有 通过将边延伸到
  • (i, p_i) 形成的图形成一棵树。
  • 所有输入均为整数 经过

入力

输入将以以下格式从标准输入给出。

N M K
p_1 p_2 ... p_{N-1} p_N

出力

K 操作后, 如果你能做到所有M 硬币都被放置, 如果不可能,例如

v_1 v_2 ... v_{M-1} v_M

如果不可能的话,比如 -1 。


入力例 1

3 2 4
2 0 2

出力例 1

1 3

通过执行以下操作: 您可以创建 \{1, 3\} 列,并且不能创建按字典顺序小于此的列。

  • 1 将第 1 个硬币放在顶部 将其放入 2 移至

操作1

  • 1 将第 1 个硬币放在顶部 将其放入 2 到 1 移至

操作2

  • 2 将第 1 个硬币放在顶部 将其放入 2 移至

操作3

  • 2 将第 1 个硬币放在顶部 将其放入 2 到 3 移至

操作4

在上图中,1 第二枚硬币是红色的,2 第二枚硬币显示为蓝色。


入力例 2

3 2 5
2 0 2

出力例 2

-1

5 无法执行,因此 -1 输出。