Submission #397638

#TimeUsernameProblemLanguageResultExecution timeMemory
397638IwanttobreakfreeNetwork (BOI15_net)C++98
0 / 100
1 ms204 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int>sol;
void dfs(int a,int b,vector<vector<int> >& v){
	for(int x:v[a]){
		if(x!=b){
			dfs(x,a,v);
		}
	}
	if(v[a].size()==1)sol.push_back(a+1);
}
int main(){
	int n,a,b;
	cin>>n;
	vector<vector<int> >v(n,vector<int>());
	for(int i=0;i<n-1;i++){
		cin>>a>>b;
		a--;b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0,-1,v);
	int k=sol.size();
	if(k%2){
		cout<<k/2+1<<'\n';
		for(int i=0;i<k-2;i+=2)cout<<sol[i]<<' '<<sol[i+1]<<'\n';
		cout<<sol[k-1]<<' '<<sol[0]<<'\n';
	}
	else{
		cout<<k/2<<'\n';
		for(int i=0;i<k;i+=2)cout<<sol[i]<<' '<<sol[i+1]<<'\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...