Submission #1127363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127363		Muhammet	Network (BOI15_net)	C++20	100 / 100	349 ms	45304 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define SZ(s) (int)s.size()

vector <vector <int>> v;

vector <pair<int,int>> ans;

vector <int> v1;

int n, a, b, cn;

void dfs(int x, int y = -1){
	for(auto i : v[x]){
		if(i == y) continue;
		dfs(i,x);
	}
	if(SZ(v[x]) == 1) v1.push_back(x);
	return;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;
	v.resize(n+1);
	for(int i = 1; i < n; i++){
		int u1, u2;
		cin >> u1 >> u2;
		v[u1].push_back(u2);
		v[u2].push_back(u1);
	}
	dfs(1);
	cout << (SZ(v1)+1)/2 << '\n';
	int x = (SZ(v1))/2;
	for(int i = 0; i < (SZ(v1)+1)/2; i++){
		cout << v1[i] << ' ' << v1[i+x] << '\n';
	}
	// if(SZ(v1) % 2 == 1) cout << v1.back() << ' ' << v1[SZ(v1)-2] << '\n';
}

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