Submission #1173350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173350		Nurislam	Network (BOI15_net)	C++20	0 / 100	0 ms	324 KiB

net

#include <bits/stdc++.h>

using namespace std;


#define int long long
//#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;
const int N = 1e5 + 5;


void solve(){
	int n;
	cin >> n;
	vector<vector<int>> g(n+1);
	for(int i = 1; i < n; i ++ ) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	int root = 1;
	while(g[root].size() == 1) root ++ ;
	
	
	vector<array<int,2>> ans;
	function<vector<int>(int,int)> dfs = [&] (int ps, int pr){
		if(g[ps].size() == 1) {
			vector<int> res = {ps};
			return res;
		};
		
		
		vector<int> cur;
		for(int to : g[ps]) 
			if(to != pr){
				vector<int> res = dfs(to, ps);
				if(cur.size() == 0) cur = res;
				else {
					if(cur.size() < res.size())swap(cur, res);
					
					if(root == ps) {
						while(cur.size()+res.size() > 3 && res.size()) {
							ans.push_back({res.back(), cur.back()});
							cur.pop_back();
							res.pop_back();
						}
						for(int i:res)cur.push_back(i);
						continue;
					}
					
					while(cur.size() > 1 && res.size()) {
						ans.push_back({res.back(), cur.back()});
						cur.pop_back();
						res.pop_back();
					}
					for(int i:res)cur.push_back(i);
				}
			}
		//cout << ":" << ps << '\n';
		//for(auto i : cur)cout << i << ' ';
		//cout << '\n';
		return cur;
	};
	
	//cout << root << '\n';
	
	vector<int> res = dfs(root, root);
	
	for(int i = 1; i < res.size(); i += 2)
		ans.push_back({res[i], res[i-1]});
		
	if(res.size()%2 == 1) 
		ans.push_back({res[res.size()-2], res.back()});
	
	
	cout << ans.size() << '\n';
	for(auto [a, b] : ans)cout << a << ' ' << b << '\n';
	
};



signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

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