Submission #656037

#	Time	Username	Problem	Language	Result	Execution time	Memory
656037		Mohammad_Parsa	Network (BOI15_net)	C++14	100 / 100	601 ms	41544 KiB

net

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define mk make_pair

const int N=5e5+7;

vector<int>vec[N],barg;

void dfs(int v,int p){
	if(vec[v].size()==1) barg.pb(v);
	for(auto u:vec[v]){
		if(u!=p) dfs(u,v);
	}
}


int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	int u,v;
	for(int i=0;i<n-1;i++){
		cin>>u>>v;
		vec[v].pb(u);
		vec[u].pb(v);
	}
	if(n==2){
		cout<<1<<endl<<1<<" "<<2;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(vec[i].size()!=1){
			dfs(i,i);
			break;
		}
	}
	int x=barg.size()/2+(barg.size()%2);
	cout<<x<<endl;
	for(int i=0;i<x;i++){
		cout<<barg[i]<<" "<<barg[(i+x)%barg.size()]<<endl;
	}
	
}

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