Submission #9697251

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
#define MAXN 100100

int A[MAXN];
int gone[MAXN];
vi V[MAXN];
vi V2[MAXN];
int N,a,b;
vpi E;
vi l,res;

void dfs(int x, int p){
	// cout<<"Safe "<<x<<'\n';
	l.pb(A[x]);
	for (auto v:V[x])if(v!=p && !gone[v]){
		dfs(v,x);
	}
}

int main(){
	cin>>N;
	if (N == 2){
		cout<<"1 2";
		return 0;
	}
	for (int i=1;i<N;++i){
		cin>>a>>b;
		E.pb(a,b);
		V[a].pb(b);V[b].pb(a);
	}
	for (int i=1;i<=N;++i)if(SZ(V[i]) == 1)gone[i] = 1;
	for (auto i : E){
		if (gone[i.f]){
			++A[i.s];
		}else if(gone[i.s]){
			++A[i.f];
		}
	}
	// for (int i=1;i<=N;++i)cout<<gone[i]<<' ';cout<<'\n';
	for (auto i : E){
		// cout<<i.f<<' '<<i.s<<' '<<gone[i.f]<<' '<<gone[i.s]<<'\n';
		if (gone[i.s] || gone[i.f])continue;
		V2[i.f].pb(i.s);
		V2[i.s].pb(i.f);
		// cout<<i.f<<' '<<i.s<<'\n';
	}
	for (int i=1;i<=N;++i)if(SZ(V2[i]) > 2){
		cout<<-1;
		return 0;
	}
	for (int i=1;i<=N;++i){
		if (A[i] >= 1){
			dfs(i,-1);
			break;
		}
	}
	if (SZ(l) == 0)assert(0);
	sort(ALL(l));
	int t = 1;
	for (auto i:l){
		// cout<<"Do "<<i<<'\n';
		if (i == 0){
			res.pb(t);
			++t;
			continue;
		}
		if (SZ(res) == 0){
			res.pb(1);
			for (int j=3;j<t+i;++j)res.pb(j);
			if (i >= 1)res.pb(2);
			if (i >= 2)res.pb(i+t);
			t = t+i+1;
			continue;
		}
		for (int k=t+1;k<t+i;++k){
			res.pb(k);
		}
		res.pb(t);
		res.pb(t+i);
		t = t+i+1;
	}

	assert(SZ(res) == N);
	for (auto i:res){cout<<i<<' ';assert(i<=N);}
}

Submission Info

Judge Result