제출 #954436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954436		amirhoseinfar1385	Network (BOI15_net)	C++17	100 / 100	382 ms	47780 KiB

net

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int n;
vector<int>adj[maxn];

void vorod(){
	cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}
vector<int>allv;
vector<pair<int,int>>res;

void dfs(int u,int par=-1){
	if((int)adj[u].size()==1){
		allv.push_back(u);
		return ;
	}
	for(auto x:adj[u]){
		if(x!=par){
			dfs(x,u);
		}
	}
}

void pre(){
	for(int i=1;i<=n;i++){
		if((int)adj[i].size()>1){
			dfs(i);
			break;
		}
	}
	int sz=allv.size();
	for(int i=0;i<sz/2;i++){
		res.push_back(make_pair(allv[i],allv[i+sz/2]));
	}
	if(sz&1){
		res.push_back(make_pair(allv[0],allv.back()));
	}
}

void khor(){
	int sz=res.size();
	cout<<sz<<"\n";
	for(auto x:res){
		cout<<x.first<<" "<<x.second<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	khor();
}

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