제출 #1127245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127245		Halym2007	Network (BOI15_net)	C++17	0 / 100	8 ms	12100 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 5e5 + 5;

int n, uzyn[N];
vector <int> v[N];
pii jog; 


void dfs (int x, int par, int h) {
	uzyn[x] = h;
	for (int i : v[x]) {
		if (i == par) continue;
		dfs (i, x, h + 1);
	}
}


int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		v[l].pb (r);
		v[r].pb (l);
	}
	dfs (1, -1, 1);
	vector <pii> kk;
	for (int i = 1; i <= n; ++i) {
		if ((int)v[i].sz == 1) {
			kk.pb ({uzyn[i], i});
		}
	}
	sort (kk.begin(), kk.end());
//	reverse (kk.begin(), kk.end());
//	for (auto i : kk) {
//		cout << i.ff << " " << i.ss << "\n";
//	}
//	cout << "\n\n";
	assert ((int)kk.sz > 1);
	cout << ((int)kk.sz + 1) / 2 << "\n";
	cout << kk[0].ss << " " << kk.back().ss << endl;
	kk.pop_back();
	kk.pb ({0, 1});
	for (int i = 2; i < (int)kk.sz; i += 2) {
		cout << kk[i - 1].ss << " " << kk[i].ss << endl;
	}
}
/*
6
1 2
2 3
2 4
5 4
6 4

8
1 2
2 3
3 4
4 5
3 6
3 7
3 8
*/

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