Submission #79586

#TimeUsernameProblemLanguageResultExecution timeMemory
79586combi1k1Network (BOI15_net)C++14
100 / 100
649 ms59428 KiB
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define X   first
#define Y   second
#define pb  push_back

const int   N   = 5e5 + 1;

typedef pair<int,int>   ii;

vector<int> g[N];
vector<ii>  res;

ii  dfs(int u,int p)    {
	if (g[u].size() == 1)   return ii(u,0);
	ii  ans = ii(0,0);
	for(int v : g[u])
		if (v != p) {
			ii  cur = dfs(v,u);
			if (!ans.X) {
				ans = cur;
				continue;
			}
			if (!ans.Y) {
				if (cur.Y)  {
					res.pb({ans.X,cur.X});
					ans.X = cur.Y;
				}
				else
					ans.Y = cur.X;
				continue;
			}
			res.pb({ans.Y,cur.X});
			ans.Y = cur.Y;
		}
	return ans;
}

signed main()   {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n;  cin >> n;
	
	for(int i = 1 ; i < n ; ++i)    {
		int x, y;   cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	for(int i = 1 ; i <= n ; ++i)
		if (g[i].size() > 1)    {
			ii  cur = dfs(i,0);
			if (!cur.Y) cur.Y = i;
			res.pb({cur.X,cur.Y});
			break;
		}
		
	cout << res.size() << "\n";
	
	for(ii e : res) cout << e.X << " " << e.Y << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...