Submission #952578

#TimeUsernameProblemLanguageResultExecution timeMemory
952578PM1Network (BOI15_net)C++17
100 / 100
363 ms49616 KiB
#include <bits/stdc++.h>
using namespace std;
const int mxn=5e5+5;
int n,k,root,par[mxn];
vector<int>v[mxn],leaf;
void dfs(int z){
	bool  cnt=0;
	for(auto i:v[z]){
		if(par[z]!=i){
			cnt=1;
			par[i]=z;
			dfs(i);
		}
	}
	if(!cnt)
		leaf.push_back(z);
}
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;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(v[i].size()>1){
			root=i;
			break;
		}
	}
	dfs(root);
	k=(leaf.size()+1)/2;
	cout<<k<<'\n';
	for(int i=1;i<=k;i++){
		cout<<leaf[i-1]<<" "<<leaf[min((int)leaf.size()-1,i+k-1)]<<'\n';
	}
	return 0;

} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...