Submission #1282796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282796		Jawad_Akbar_JJ	Network (BOI15_net)	C++20	100 / 100	274 ms	45288 KiB

net

#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';
}

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