Submission #1171007

#TimeUsernameProblemLanguageResultExecution timeMemory
1171007ZeroCoolNetwork (BOI15_net)C++20
100 / 100
196 ms57924 KiB
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

const int N = 1e6 + 20;
const int K = 469;
const int LOG = 26;
const int INF = 1e12;	
int MOD = 998244353;

vector<int> g[N];
vector<int> ord;

void dfs(int x, int p){
	if(g[x].size() == 1)ord.push_back(x);
	for(auto u: g[x]){
		if(u == p)continue;
		dfs(u, x);
	}
}

void orz(){
	int n;
	cin>>n;
	for(int i = 1;i < n;i++){
		int a, b;
		cin>>a>>b;
		--a, --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0, 0);
	int cnt = ord.size();
	cout<<(cnt + 1) / 2<<'\n';
	for(int i = 0;i < cnt / 2;i++)cout<<ord[i] + 1<<" "<<ord[i + cnt / 2] + 1<<'\n';
	if(cnt % 2)cout<<ord[0] + 1<<" "<<ord[cnt - 1] + 1;
}	
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	//cin>>t;
	t = 1;
	while(t--)orz();
}
	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...