Submission #556742

#	Time	Username	Problem	Language	Result	Execution time	Memory
556742		Hanksburger	Network (BOI15_net)	C++17	100 / 100	430 ms	47724 KiB

net

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[500005], vec;
void dfs(int u, int p)
{
	if (adj[u].size()==1)
		vec.push_back(u);
	for (int v:adj[u])
		if (v!=p)
			dfs(v, u);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, sz;
	cin >> n;
	for (int i=1; i<n; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	sz=vec.size();
	cout << (sz+1)/2 << '\n';
	for (int i=0; i<(sz+1)/2; i++)
		cout << vec[i] << ' ' << vec[i+sz/2] << '\n';
	return 0;
}

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