Submission #1227890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227890		jellybean	Network (BOI15_net)	C++20	100 / 100	305 ms	74240 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<' '<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;

const int N = 5e5+5;
vector<int>adj[N], v[N];
int sz[N];

void dfs(int x, int p){
	if(adj[x].size() == 1) sz[x] = 1;
	else sz[x] = 0;
	for(auto i:adj[x]){
		if(i==p) continue;
		dfs(i,x);
		sz[x] += sz[i];
	}
}

int findc(int x, int p, int n){
	int centriod = x;
	
	for(auto i:adj[x]){
		if(i==p) continue;
		if(sz[i] > n/2){
			centriod = findc(i,x,n);
		}
	}
	
	return centriod;
}

void dfs2(int x, int p, int h){
	if(adj[x].size() == 1) v[h].pb(x);
	for(auto i:adj[x]){
		if(i==p) continue;
		dfs2(i,x,h);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=0; i<n-1; i++){
		int a,b; cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	
	dfs(1,-1);
	int cn = findc(1,-1,sz[1]);
	
	dfs(cn,-1);
	
	priority_queue<pii>pq;
	for(auto i:adj[cn]){
		dfs2(i,cn,i);
		pq.push({v[i].size(), i});	
	}
	
	cout<<(sz[cn]+1)/2<<'\n';
	
	while(pq.size() > 1){
		auto[a,b] = pq.top(); pq.pop();
		auto[c,d] = pq.top(); pq.pop();
		
		cout<<v[b].back()<<' '<<v[d].back()<<'\n';
		v[b].pop_back();
		v[d].pop_back();
		
		if(a-1) pq.push({a-1,b});
		if(c-1) pq.push({c-1,d});
	}
	
	if(pq.size()){
		auto[a,b] = pq.top(); pq.pop();
		cout<<v[b].back()<<' '<<cn<<'\n';
	}
	
	return 0;
}

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