Submission #1048074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048074		soroostab	Network (BOI15_net)	C++14	100 / 100	341 ms	42888 KiB

net

#include <bits/stdc++.h>
#define ll long long int
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pcc pair<char,char>
#define pbb pair<bool,bool>
#define PB push_back
#define PF push_front
#define MOD 1000000007
#define intxt freopen("input.txt","r",stdin)
#define outtxt freopen("output.txt","w",stdout)

using namespace std;

const int MAXN = 5e5 + 10;
int n ,q1 ,q2 ,ans;
vector <int> adj[MAXN];
vector <int> leaf;

inline void dfs(int v , int p = 0) {
	bool c = 0;
	for(auto u : adj[v]) {
		if(u == p) {
			continue;
		}
		dfs(u , v);
		c = 1;
	}
	if(!c) {
		ans++;
		leaf.PB(v);
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	
	cin >> n;
	
	for(int i = 1 ; i < n ; i++) {
		cin >> q1 >> q2;
		adj[q1].PB(q2);
		adj[q2].PB(q1);
	}
	
	for(int i = 1 ; i <= n ; i++) {
		if(adj[i].size() > 1) {
			dfs(i);
			break;
		}
	}
	
	if(ans == 1) {
		cout << 0 << endl;
		return 0;
	}
	int k = ans / 2;
	cout << (ans + 1) / 2 << endl;
	for(int i = 0 ; i < k ; i++) {
		cout << leaf[i] << " " << leaf[i + k] << endl;
	}
	if(ans % 2 == 1) {
		cout << leaf[leaf.size() - 1] << " " << leaf[0];
	}
}
// Hello

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