题意:有一个\(n\)个结点的树,给你\(n-1\)个\(a_i\)和\(b_i\),表示将第\(i\)条边断开后两个连通块中的最大顶点,现在要你根据给出的信息还原出这颗树.
题解:首先无论怎么分,\(a_i\)和\(b_i\)中一定有一个是的值是\(n\).然后我们将顶点排序,按照\(n\)为根结点来构造.那么序列中出现次数最少的那个点,可以将其构造成叶子结点.出现次数第二小的可以作为叶子结点的父结点,以此类推.最后将没出现的数插入到两点之间(一定要小于父亲结点)即可,
代码:
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define me memset #define rep(a,b,c) for(int a=b;a<=c;++a) #define per(a,b,c) for(int a=b;a>=c;--a) const int N = 1e6 + 10; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; using namespace std; typedef pair<int,int> PII; typedef pair<ll,ll> PLL; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll lcm(ll a,ll b) {return a/gcd(a,b)*b;} int n; int a[N]; int ans[N]; bool vis[N]; int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<n;++i){ int x,y; cin>>x>>y; if(y!=n){ cout<<"NO\n"; return 0; } a[i]=x; } sort(a+1,a+n); a[n]=n; for(int i=1;i<=n;++i){ if(!vis[a[i]]){ ans[i]=a[i]; vis[a[i]]=true; } else{ bool flag=false; for(int j=1;j<a[i];++j){ if(!vis[j]){ ans[i]=j; vis[j]=true; flag=true; break; } } if(!flag){ cout<<"NO\n"; return 0; } } } cout<<"YES\n"; for(int i=2;i<=n;++i){ cout<<ans[i]<<' '<<ans[i-1]<<'\n'; } return 0; }
Codeforces Round #730 (Div. 2)