← 返回题目列表

AtCoder · nikkei2019_2_final_d

D. 木、

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

配点 : 800 点

問題文

斯肯努君是 n+1 顶点树 我有 T 。 这棵树 T 的每个顶点写入一个整数,并且每个 1,2,..., n+1 。 树 T 有边缘 n 书籍可用,i 第边是 具有 i 和的顶点 它连接标有 v_i 的顶点。

趁着努助君不注意的时候,努助君走向了树。 我在 T 上做了以下恶作剧。 在

  1. 木 T 的顶点中,度数为 1 顶点就是 1 选择一个,将其删除,然后隐藏它。
  2. 仍然存在 删除写在 n 顶点上的所有整数 每个
  3. 仍然存在 删除写在 n 顶点的新整数。 一一添加 1,2,..., n 一一添加

努助君恶作剧后的树 我们称之为 T' 。 树 T' 有边缘 n-1 书籍可用, i 第边是 具有 i 和的顶点 它连接标有 u_i 的顶点。

当Skenu注意到努助君的恶作剧时,他想猜测努助君隐藏顶点上的整数。找到所有可能的整数,并按升序打印它们。

制約

  • 2\leq n \leq 2\times 10^5
  • i=1, 2, \dots, n 关于 1\leq v_i \leq n+1
  • i=1, 2, \dots, n-1 关于 1\leq u_i \leq n
  • T (辺 (1, v_1), (2, v_2), \dots, (n, v_{n}) ) 形成一棵树
  • T' (辺(1, u_1), (2, u_2), \dots, (n-1, u_{n-1})) 形成一棵树
  • 努助君隐藏的巅峰可能是什么? 1 存在多个
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

n
v_1 v_2 \dots v_n
u_1 u_2 \dots u_{n-1}

出力

请将可以写在 Nusuke-kun 的隐藏顶点上的所有整数按升序输出在一行上,并用空格分隔。


入力例 1

10
2 9 2 2 2 2 6 7 10 11
2 3 4 10 4 5 4 4 4

出力例 1

8 11

次数 1 的顶点是 这是写入 1,3,4,5,8,11 的顶点。 隐藏写入

例如, 经过 11 的顶点后,如果添加一个新的整数,如下所示,树将是 匹配 T' 。

另外,8 的顶点后,如果添加一个新的整数,如下所示,树将是 匹配 T' 。

当隐藏除此之外的顶点时,无论你如何写整数,树 T' 是不可能的,所以答案是按升序排列它们。 这是写入 8 11 。


入力例 2

5
6 1 1 1 1
5 5 5 5

出力例 2

2 3 4 5 6

次数 1 的顶点是 这是写入 2,3,4,5,6 的顶点。 无论删除哪一个,如果正确添加整数,都可以创建一棵树。 您可以创建与 T' 相同的东西,所以 请打印所有这些内容。


入力例 3

5
4 3 4 5 6
2 3 4 5

出力例 3

1

努助君隐藏的顶部是 斯肯努君可以看到上面写着 1 。