Submission #390218

#TimeUsernameProblemLanguageResultExecution timeMemory
390218ritul_kr_singhNetwork (BOI15_net)C++17
100 / 100
516 ms43280 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

vector<vector<int>> g;
vector<int> leaves;

void dfs(int u, int p){
	if(g[u].size() == 1) leaves.push_back(u);
	for(int v : g[u]) if(v != p) dfs(v, u);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, a, b; cin >> n;
	g.resize(n);
	for(int i=1; i<n; ++i){
		cin >> a >> b; --a, --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0, 0);
	int c = leaves.size();
	cout << (c+1)/2 nl;
	for(int i=0; i<c/2; ++i) cout << leaves[i]+1 sp leaves[i+c/2]+1 nl;
	if(c & 1) cout << leaves[0]+1 sp leaves[c-1]+1 nl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...