题解：CF1283F DIY Garland

· · 题解

清新小构造。

显而易见 a_1 一定是根节点。

一根导线的重要性是如果切断这根导线所有因此与电源断开的灯的亮度值之和，相当于是这根导线连接的儿子的子树亮度和。

又因为第 i 盏灯的亮度是 2^i，所以所有比 i 小的彩灯的亮度和小于 2^i。

所以一根导线的重要性也相当于这个导线所连儿子的子树的彩灯最大值（最大值相等则深度越深重要性越小）。

然后又因为导线重要性是所连儿子子树的彩灯最大值，所以题目给的 a 数组相当于是给出了若干条链。

我的思路大概是这样：扫描 a_2 到 a_n，扫描过程中，对于每个 a_i：

如果 a_i 没被连过并且 a_i 不是当前未被连过的彩灯的最大值，说明未被连过的最大值还在 a_i 的子树中，就连上 a_{i-1} 和 a_i。

如果 a_i 没被连过并且 a_i 是当前未被连过的彩灯的最大值，说明 a_i 是其子树的最大值，且新的最大值还是在 a_i 的子树内，就把 a_{i-1} 和 a_i 连上。

如果 a_i 被连过，说明 a_{i-1} 是其子树最大值的儿子，且新的最大值不在 a_{i-1} 子树内，就把 a_{i-1} 和当前未被连过的彩灯最大值连上。

代码：

#include<bits/stdc++.h>
#define ft first
#define sd second
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
int a[N],len,n;
bool st[N];
PII ans[N];
priority_queue<int,vector<int>,less<int>> q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        q.push(i);
    }
    int fa=a[1];
    st[a[1]]=true;
    for(int i=2;i<n;i++){
        while(q.size()&&st[q.top()]) q.pop();
//      printf("q[%d].top() = %d\n",i,q.top());
//      if(i==4) printf("st[5] = %d\n",st[5]);
        if(st[a[i]]){
            ans[++len]={fa,q.top()}; 
            st[q.top()]=true;   
            q.pop();
//          if(i==3) printf("q.top() = %d\n",q.top());
            fa=a[i];
        }else{
            ans[++len]={fa,a[i]};
            st[a[i]]=true;
            fa=a[i];
        }
    }
    while(q.size()){
        if(st[q.top()]){
            q.pop();
            continue;
        }
        ans[++len]={fa,q.top()};
        st[q.top()]=true;
        fa=q.top();
        q.pop();
    }
    if(len!=n-1){
        puts("-1");
        return 0;
    }
    printf("%d\n",a[1]);
    for(int i=1;i<=len;i++){
        printf("%d %d\n",ans[i].ft,ans[i].sd);
    }
    return 0;
}