Submission #160528

#	Time	Username	Problem	Language	Result	Execution time	Memory
160528		dolphingarlic	Network (BOI15_net)	C++14	100 / 100	1018 ms	47860 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[500001], leaves;
 
void dfs(int node = 1, int parent = 0) {
	if (graph[node].size() == 1) leaves.push_back(node);
	for (int i : graph[node]) {
		if (i == parent) continue;
		dfs(i, node);
	}
}
 
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs();

	cout << (leaves.size() + 1) / 2 << '\n';
	for (int i = 0; i + leaves.size() / 2 < leaves.size(); i++) cout << leaves[i] << ' ' << leaves[i + leaves.size() / 2] << '\n';
	return 0;
}

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