Submission #79567

#	Time	Username	Problem	Language	Result	Execution time	Memory
79567		DrumpfTheGodEmperor	Network (BOI15_net)	C++14	100 / 100	660 ms	41596 KiB

net

#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1061109567
#define INFLL 4557430888798830399
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
const int N = 5e5 + 5;
typedef pair<int, int> ii;
int n;
bool used[N];
vector<int> g[N], leafs;
vector<ii> edges;
void dfs(int u, int p) {
	if (g[u].size() == 1) leafs.pb(u);
	fa (v, g[u]) if (v != p) dfs(v, u);
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fw (i, 1, n) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].pb(v), g[v].pb(u);
	}
	int root = -1;
	fw (i, 0, n) if (g[i].size() > 1) {
		root = i;
		break;
	}
	dfs(root, -1);
	int tmp = leafs.size();
	cout << (tmp + 1) / 2 << "\n";
	if (tmp & 1) {
		cout << root + 1 << " " << leafs[tmp / 2] + 1 << "\n";
		fw (i, 0, tmp / 2) cout << leafs[i] + 1 << " " << leafs[i + tmp / 2 + 1] + 1 << "\n";
	} else {
		fw (i, 0, tmp / 2) cout << leafs[i] + 1 << " " << leafs[i + tmp / 2] + 1 << "\n";
	}
	return 0;
}

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