Submission #1282796

#TimeUsernameProblemLanguageResultExecution timeMemory
1282796Jawad_Akbar_JJNetwork (BOI15_net)C++20
100 / 100
274 ms45288 KiB
#include <iostream>
#include <vector>

using namespace std;
vector<int> nei[1<<19], vec;

void dfs(int u, int p = 0, int ch = 0){
	for (int i : nei[u]){
		if (i != p)
			dfs(i, u), ch++;
	}
	if (ch == 0)
		vec.push_back(u);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin>>n;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;

		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	for (int i=1;i<=n;i++){
		if (nei[i].size() > 1)
			dfs(i), i = n;
	}

	n = vec.size();
	cout<<(n + 1) / 2<<'\n';
	
	if (n % 2 == 1)
		cout<<vec[0]<<" "<<vec[n / 2]<<'\n';
	for (int i=0;i < n / 2;i++)
		cout<<vec[i]<<" "<<vec[i + (n + 1) / 2]<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...