Submission #139842

#	Time	Username	Problem	Language	Result	Execution time	Memory
139842		Saboon	Network (BOI15_net)	C++14	100 / 100	1274 ms	92900 KiB

net

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int maxn = 5e5 + 10;
 
int par[maxn], sz[maxn];
vector<int> t[maxn];
 
int cnt;
vector<int> a[maxn];
 
void DFS(int v, int par = -1){
	bool leaf = 1;
	for (auto u : t[v]){
		if (u != par){
			DFS(u, v);
			leaf = 0;
		}
		if (par == -1)
			cnt ++;
	}
	if (leaf){
		a[cnt].push_back(v);
	}
}
 
int dfs(int v, int par = -1){
	for (auto u : t[v])
		if (u != par)
			sz[v] += dfs(u, v);
	if (sz[v] == 0)
		sz[v] = 1;
	return sz[v];
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	if (n == 2)
		return cout << 1 << endl << 1 << " " << 2 << endl, 0;
	int root;
	for (root = 1; root <= n; root ++)
		if (t[root].size() > 1)
			break;
	dfs(root);
	int v = root, Max = sz[root], parent = -1;
	bool found = 1;
	while (found){
		found = 0;
		for (auto u : t[v]){
			if (u != parent and 2 * sz[u] >= Max){
				parent = v;
				v = u;
				found = 1;
				break;
			}
		}
	}
	DFS(v);
	vector<pair<int, int> > ans;
	set<pair<int, int> > s;
	for (int i = 0; i < cnt; i++){
		int k = a[i].size();
		s.insert({-k, i});
	}
	while (!s.empty()){
		if (s.size() == 1){
			int fi = (*s.begin()).second;
			ans.push_back({a[fi].back(), v});
			break;
		}
		int fi = (*s.begin()).second;
		s.erase(s.begin());
		int se = (*s.begin()).second;
		s.erase(s.begin());
		ans.push_back({a[fi].back(), a[se].back()});
		a[fi].pop_back();
		if (!a[fi].empty())
			s.insert({-a[fi].size(), fi});
		a[se].pop_back();
		if (!a[se].empty())
			s.insert({-a[se].size(), se});
	}
	cout << ans.size() << endl;
	for (auto it : ans)
		cout << it.first << " " << it.second << endl;
}

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