Submission #239849

#	Time	Username	Problem	Language	Result	Execution time	Memory
239849		kshitij_sodani	Network (BOI15_net)	C++17	100 / 100	827 ms	57720 KiB

net

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second



int n;
vector<int> adj[500001];
int co=0;
vector<int> kk;
void dfs(int no,int par=-1){
	vector<pair<int,int>> ss[2];
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
			/*cout<<j<<','<<x[0]<<","<<x[1]<<endl;
			if(x.size()==1){
				ss[0].pb({x[0],-1});
			}
			else{
				ss[1].pb({x[0],x[1]});
			}*/
		}
	}
	if(adj[no].size()==1){
		co+=1;
		kk.pb(no);
	}
/*	if(no==3){
		cout<<','<<ss[1].size()<<","<<ss[0].size()<<endl;
	}
	if(ss[1].size()%2==0){
		for(int i=0;i<(int)(ss[1].size());i+=2){
			ans.pb({ss[1][i].a,ss[1][i+1].a});
			ans.pb({ss[1][i].b,ss[1][i+1].b});

		}

		if(ss[0].size()==0){
			pair<int,int> x=ans.back();
			ans.pop_back();
			return {x.a,x.b};
		}

		for(int i=0;i<(int)(ss[0].size())-1;i+=2){
			ans.pb({ss[0][i].a,ss[0][i+1].a});
		}
		if(ss[0].size()%2==0){
			ans.pop_back();
			return {ss[0].back().a,ss[0][ss[0].size()-2].a};
		}
		else{
			return {ss[0].back().a};
		}
	}
	else{
		for(int i=0;i<(int)(ss[1].size())-1;i+=2){
			ans.pb({ss[1][i].a,ss[1][i+1].a});
			ans.pb({ss[1][i].b,ss[1][i+1].b});
		}
		for(int i=0;i<(int)(ss[0].size())-1;i+=2){
			ans.pb({ss[0][i].a,ss[0][i+1].a});
		}
		if(ss[0].size()%2==0){
			return {ss[1].back().a,ss[1].back().b};
		}
		else{
			ans.pb({ss[1].back().a,ss[0].back().a});
			return {ss[1].back().b};
		}
	}

*/

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		adj[aa-1].pb(bb-1);
		adj[bb-1].pb(aa-1);

	}
	int r=0;
	for(int i=0;i<n;i++){
		if(adj[i].size()>1){
			r=i;
		}
	}
	dfs(r);
	cout<<(co+1)/2<<endl;

	for(int i=0;i<(co+1)/2;i++){
	//	cout<<i<<endl;
		cout<<kk[i]+1<<" "<<kk[i+co/2]+1<<endl;
	}
/*	for(int i=0;i<kk.size()/2;i++){
		cout<<kk[i]+1<<" "<<kk[kk.size()-i-1]+1<<endl;
	}
	if(kk.size()%2==1){
		cout<<kk[kk.size()/2]+1<<" "<<r+1<<endl;
	}*/


	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37