Submission #848230

#	Time	Username	Problem	Language	Result	Execution time	Memory
848230		Hakiers	Network (BOI15_net)	C++17	100 / 100	544 ms	77084 KiB

net

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
vector<int> G[MAXN];
int parent[MAXN];
pair<int, int> dp[MAXN];
tuple<int, int, int> vein;
vector<vector<int>> Q;
vector<int> xd;
int n;

void dfsVein(int v, int p){

	if((int)G[v].size() == 1) dp[v].second = v;
	else dp[v].first = -1;
	
	int max1 = v;
	for(auto u : G[v]){
		if(u == p) continue;
		dfsVein(u, v);
		
		if(dp[u].first > dp[max1].first)
			max1 = u;
	}
	
	
	// albo merguje ui z uj lub ide w gore
	
	for(auto u : G[v])
		if(u != p && u != max1) vein = max(vein, make_tuple(dp[u].first + dp[max1].first + (int)G[v].size() - 2, dp[max1].second, dp[u].second));
		
	

	dp[v] = dp[max1];
	dp[v].first += max((int)G[v].size() - 2, 0);
}

void dfs(int v, int p){
	parent[v] = p;
	
	for(auto u : G[v])
		if(u != p) dfs(u, v);
	
}

void dfs_push(int v, int p){
	
	for(auto u : G[v])
		if(u != p) dfs_push(u, v);
	
	if((int)G[v].size() == 1) xd.push_back(v);

}


void compute(int u, int v){
	while(u != v){
		
		for(auto w : G[parent[u]]){
			if(w == u || w == parent[parent[u]]) continue;
			xd.clear();
			xd.shrink_to_fit();
			dfs_push(w, parent[u]);
			Q.push_back(xd);
		}
		
		u = parent[u];
	}

}

bool cmp(vector<int> &a, vector<int> &b){
	return (int)a.size() > (int)b.size();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	dfsVein(1, 1);
	auto [val, u1, u2] = vein;
	dfs(u1, u1);
	compute(u2, u1);
	sort(Q.begin(), Q.end(), cmp);
	/*
	cout << " val: " << val << " u1: " << u1 << " u2:" << u2 << endl;
	
	for(auto x : Q){
		while(x.size()){
			cout << (int)x.front() << " ";
			x.pop();
		}
		cout << endl;
	}
	*/
	vector<pair<int, int>> anserw;
	anserw.push_back({u1, u2});
	
	queue<int> sajz;
	
	
	for(auto x : Q){
		int it = 0;
		
		for(; it < (int)x.size() && sajz.size(); it++){
			anserw.push_back({x[it], sajz.front()});
			sajz.pop();
		}
		
		for(; it < (int)x.size(); it++)
			sajz.push(x[it]);
		/*
		while(Q[x].size() && sajz.size()){
			anserw.push_back({Q[x].front(), sajz.front()});
			Q[x].pop();
			sajz.pop();
		}
		
		while(Q[x].size()){
			sajz.push(Q[x].front());
			Q[x].pop();
		}
		*/
	}
	
	while(sajz.size()){
		anserw.push_back({u1, sajz.front()});
		sajz.pop();
	}
	
	cout << anserw.size() << "\n";
	for(auto [x, y] : anserw)
		cout << x << " " << y << "\n";
	
	
	
}


/*

27
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
8 10
8 11
8 12
5 13
13 14
14 15
14 16
14 17
14 18
8 19
4 20
20 21
21 22
21 23
21 24
21 25
21 26
2 27
*/

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