Codeforces 1283 F DIY Garland ——想法

This way

題意：

現在有n個點，第i個點的權值為 2 i 2^i 2i，現在有n-1條邊使得這些點組成一棵樹，邊的權值是它連接配接的子樹的權值和。現在按照邊的權值從大到小給你每條邊的父節點，讓你輸出根節點的下标以及輸出輸入順序每條邊所連接配接的兩個點

題解：

自頂向下我覺得做不了，但是反過來一想自底向上很簡單，首先我們處理出所有未出現過的點是什麼，然後最後一條邊連接配接的一定是最小的那個點。有了這個思路我們就可以很容易的想到如果我們從後往前做，那麼目前的點連接配接的一定是可供選擇的點中的子樹的值最小的那個。由于每個點的值是2的幂次，于是我們隻需要記錄目前點子樹中最大的點的值是什麼即可。那麼什麼是可供選擇的點？首先可供選擇的點一定是未在輸入中出現過的點，然後如果目前點還在前面的輸入中出現過，那麼就證明這個點還連着值更大的兒子，那麼這個點就不能被判為可供選擇的點。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=2e5+5;
int vis[N];
struct node
{
    int id,mx;
    bool operator< (const node& a)const
    {
        return mx>a.mx;
    }
};
priority_queue<node>Q;
int fa[N];
pa ans[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)scanf("%d",&fa[i]),vis[fa[i]]++;
    for(int i=1;i<=n;i++)
        if(!vis[i])
            Q.push({i,i});
    for(int i=n-1;i;i--){
        node now=Q.top();
        Q.pop();
        ans[i]={fa[i],now.id};
        vis[fa[i]]--;
        if(fa[i]!=fa[1]&&!vis[fa[i]])Q.push({fa[i],max(now.mx,fa[i])});
    }
    printf("%d\n",fa[1]);
    for(int i=1;i<n;i++)printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}