Submission #57131925

---

Source Code Expand

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=250005;
int n;
vector<int>e[N],VV[N];
int sz[N],rt,f[N];
void dfs1(int k1,int k2){
	sz[k1]=1;
	for(auto&x:e[k1])if(x!=k2){
		dfs1(x,k1);
		sz[k1]+=sz[x];
		f[k1]=max(f[k1],sz[x]);
	}
	f[k1]=max(f[k1],n-sz[k1]);
	if(f[k1]<f[rt])rt=k1;
}
vector<int>V;
void dfs2(int k1,int k2){
	int v=0;
	for(auto&x:e[k1])if(x!=k2&&(sz[x]&1)){
		assert(!v);
		v=x;
	}
	if(v)dfs2(v,k1);
	for(auto&x:e[k1])if(x!=v&&x!=k2){
		dfs2(x,k1);
	}
	V.pb(k1);
}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(n);
	rep(i,2,n){
		int u,v;
		rd(u),rd(v);
		e[u].pb(v),e[v].pb(u);
	}
	f[0]=1e9;
	dfs1(1,0);
	dfs1(rt,0);
	priority_queue<pair<int,int> >pq[2];
	for(auto&x:e[rt]){
		V.clear();
		dfs2(x,rt);
		reverse(V.begin(),V.end());
		VV[x]=V;
		pq[sz[x]&1].emplace(sz[x],x);
	}
	rep(_,1,n/2-1){
		assert(!pq[1].empty());
		auto u=pq[1].top();
		pq[1].pop();
		assert(!pq[0].empty());
		auto v=pq[0].top();
		pq[0].pop();
		printf("%d %d\n",VV[u.second].back(),VV[v.second].back());
		VV[u.second].pop_back();
		VV[v.second].pop_back();
		if(--u.first){
			pq[u.first&1].push(u);
		}
		if(--v.first){
			pq[v.first&1].push(v);
		}
	}
	assert(!pq[1].empty());
	printf("%d %d\n",pq[1].top().second,rt);
	return 0;
}

Submission Info

Judge Result