Prüfer Code

题目描述

一棵有 n 个结点的树的 Prüfer 码是一个长度为 n-2 的整数序列，它唯一确定了这棵树的结构。 编码构造如下：只要剩下至少三个结点，找到标签最小的叶子，将其唯一邻居的标签添加到码中，然后从树中删除该叶子。 给出一棵树的 Prüfer 码，你的任务是构造原始的树。

输入格式

第一行包含整数 n：结点数。结点编号为 1,2,$\ldots$,n。 第二行包含 n-2 个整数：Prüfer 码。

输出格式

输出 n-1 行描述树的边。每行包含两个整数 a 和 b：表示结点 a 和 b 之间有一条边。你可以按任意顺序输出这些边。

5
2 2 4

1 2
2 3
2 4
4 5

提示

$3 \le n \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1134|高级图论问题

来源

CSES1134|高级图论问题