题解 CF1283F 【DIY Garland】
Rhodoks
2020-01-07 18:33:59
出题人题解咕掉了，照着代码理解了一下写写个人的看法。
$used[i]$代表目前$i$号节点的父亲是否确定，$a[i]$是第$i$条边的主灯（父亲节点）。
算法的思想大致是这样：按照给出边的顺序遍历，$i$为边序号。如果$i<n$且第$i+1$条边的父亲未定，则连接$a[i]$与$a[i+1]$。否则连接$a[i]$和$cur$，后者为当前未确定父亲的编号最大的节点。
这样，每次连接第$i$条边时，$a[i]$的父亲都是已经确定的（$a[1]$是根节点例外）。这意味着，满足$used[i]=1$的点$i$不可能对之后的边的重要性产生贡献。
设第$i$条边的重要性是$d_i$。
如果$a[i]$连接了$cur$，因为$cur$是当前$used[i]=0$的编号最大节点，之后的边的子树中的节点编号必然小于$cur$。$2^i>2^{i-1}+2^{i-2}+...+2^1+2^0$。所以$d_i>d_j (j>i)$，特殊地，$d_i>d_{i+1}$。
如果$a[i]$连接了$a[i+1]$,那么$a[i]$是$a[i+1]$的父亲，显然$d_i>d_{i+1}$。
综上所述$d_1>d_2>...>d_{n-1}>d_n$
对于所有合法数据均能构造出这样的解，不需要考虑无解情况。
code：
```cpp
#include <bits/stdc++.h>
#define MAXN 210000
#define _ 0
using namespace std;
int n;
int a[MAXN];
int used[MAXN];
int main()
{
int n;
cin>>n;
int cur=n;
n--;
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
cout<<a[1]<<endl;
used[a[1]]=1;
for (int i=1;i<=n;i++)
{
while (used[cur])
cur--;
if (used[a[i+1]] || i==n)
{
cout<<a[i]<<' '<<cur<<endl;
used[cur]=1;
}
else
{
cout<<a[i]<<' '<<a[i+1]<<endl;
used[a[i+1]]=1;
}
}
return ~~(0^_^0);
}
```