Submission #394609

#	Time	Username	Problem	Language	Result	Execution time	Memory
394609		minoum	Network (BOI15_net)	C++17	0 / 100	9 ms	12060 KiB

net

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 5e5+10;
int n, st[MAXN], tim = 0, r, lfc = 0;
vector <int> adj[MAXN];
vector <pair<int,int>> ans;

void dfs(int v, int parv){
	st[v] = tim; tim++;
	if((int)adj[v].size()==1) ans.push_back({st[v],v});
	for(int u: adj[v])
		if(u!=parv) dfs(u,v);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; i++){
		int u,v;
		cin >> u >> v; u--; v--;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for(int i = 0; i < n; i++) lfc += ((int)adj[i].size()==1);
	for(int i = 0; i < n; i++)
		if((int)adj[i].size()>1){
			r = i; break;
		}
	if(n==2){
		cout << 1 << '\n' << "1 2" << '\n'; return 0;
	}
	dfs(r,-1);
	sort(ans.begin(), ans.end());
	cout << ((lfc+1)/2) << '\n';
	if(lfc&1){
		cout << r+1 << " " << ans.back().second+1 << '\n';
		ans.pop_back();
	}
	lfc/=2;
	for(int i = 0; i < lfc; i++) cout << ans[i].second+1 << " " << ans[i+lfc].second+1 << '\n';
	return 0; 
}

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