Submission #166920

#	Time	Username	Problem	Language	Result	Execution time	Memory
166920		super_j6	Network (BOI15_net)	C++14	100 / 100	660 ms	52184 KiB

net

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>

const int maxn = 500000;
int n;
vector<int> graph[maxn];
vector<int> lf;

void dfs(int c, int p){
	if(graph[c].size() == 1) lf.push_back(c + 1);
	for(int i : graph[c]){
		if(i == p) continue;
		dfs(i, c);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		a--, b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	dfs(0, -1);
	
	int k = (lf.size() + 1) / 2;
	cout << k << endl;
	for(int i = 0; i < k; i++) cout << lf[i] << " " << lf[i + lf.size() / 2] << endl;

	return 0;
}

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