제출 #79533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79533		Dat160601	Network (BOI15_net)	C++17	100 / 100	700 ms	43484 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n,u,v,deg[500007],ans=0;
vector <int> edge[500007],sv;
void dfs(int u,int par){
	bool leaf=true;
	for(int v:edge[u]){
		if(v==par) continue;
		dfs(v,u);
		leaf=false;
	}
	if(leaf) ans++, sv.pb(u);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		deg[u]++, deg[v]++;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	int root=-1;
	for(int i=1;i<=n;i++){
		if(deg[i]>=2){
			root=i;
			break;
		}
	}
	dfs(root,root);
	cout<<(ans+1)/2<<"\n";
	if(ans&1){
		int r=ans/2+1;
		for(int i=0;i<ans/2;i++){
			cout<<sv[i]<<" "<<sv[r]<<"\n";
			r++;
		}
		cout<<sv[ans/2]<<" "<<root<<"\n";
	}
	else{
		int r=ans/2;
		for(int i=0;i<ans/2;i++){
			cout<<sv[i]<<" "<<sv[r]<<"\n";
			r++;
		}
	}
}

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