Submission #79586

#	Time	Username	Problem	Language	Result	Execution time	Memory
79586		combi1k1	Network (BOI15_net)	C++14	100 / 100	649 ms	59428 KiB

net

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

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