「专题」构造题选讲+（可能会有的总结）
总结：
- 列出所有有用的信息及线索。
CF1283F DIY Garland
需要注意这是一道构造题而不是一道传统题，就先不要往一个特定保险的想法去靠，不然只会怎么都想不出来。
首先发现这个 \(2^i\) 肯定有特殊含义，或许会联想到 \(\sum_{j=0}^{i-1}2^j=2^i-1\)？
Feature 1：子树权值和实际上是比较子树编号最大值。
Feature 2：输入的第一个数是根。
Feature 3：没有出现的点肯定是叶子。
Feature 3 也给我们一个启发，就是倒着来的话，当且仅当这个点以后不会再出现在输入里了，这个点才有可能是当前点的儿子。于是自然想到找出度，为 \(0\) 就直接加到小根堆里。证明想想也不难。
#include
#include
#include
#include
#include
#include
#define LL long long
#define uint unsigned int
using namespace std;
const int MAXN = 2e5 + 5;
priority_queue , greater > que;
int n, a[MAXN], d[MAXN], ans[MAXN];
int main() {
scanf("%d", &n);
for(int i = 1; i < n; i ++) scanf("%d", &a[i]), d[a[i]] ++;
for(int i = 1; i <= n; i ++) if(!d[i]) que.push(i);
for(int i = n - 1; i >= 1; i --) {
if(que.empty()) { printf("-1"); return 0; }
ans[i] = que.top(); que.pop(); d[a[i]] --;
if(!d[a[i]]) que.push(a[i]);
}
printf("%d\n", a[1]);
for(int i = 1; i < n; i ++) printf("%d %d\n", a[i], ans[i]);
return 0;
}