Submission #1226317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226317		kaiboy	Network (BOI15_net)	C++20	100 / 100	179 ms	40864 KiB

net

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 500000;

vector<int> ej[N];
int qu[N], cnt;

void dfs(int p, int i) {
	if (ej[i].size() == 1) {
		qu[cnt++] = i;
		return;
	}
	for (int j : ej[i])
		if (j != p)
			dfs(i, j);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int h = 0; h < n - 1; h++) {
		int i, j; cin >> i >> j, i--, j--;
		ej[i].push_back(j);
		ej[j].push_back(i);
	}
	int r = 0;
	while (ej[r].size() == 1)
		r++;
	dfs(-1, r);
	cout << (cnt + 1) / 2 << '\n';
	for (int l = 0, r = cnt / 2; r < cnt; l++, r++)
		cout << qu[l] + 1 << ' ' << qu[r] + 1 << '\n';
	return 0;
}

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