C/C++教程

Codeforces Round #509 (Div. 2) E. Tree Reconstruction (构造,思维)

本文主要是介绍Codeforces Round #509 (Div. 2) E. Tree Reconstruction (构造,思维),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  • 题意:有一个\(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)

这篇关于Codeforces Round #509 (Div. 2) E. Tree Reconstruction (构造,思维)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!