Submission #390218

#	Time	Username	Problem	Language	Result	Execution time	Memory
390218		ritul_kr_singh	Network (BOI15_net)	C++17	100 / 100	516 ms	43280 KiB

net

#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;
}

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