oj.uz

Submission #848227

# Submission time Handle Problem Language Result Execution time Memory
848227 2023-09-11T17:28:19 Z Hakiers Network (BOI15_net) C++17
0 / 100
 106 ms 262144 KB 
#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<queue<int>> Q;
queue<int> Q[MAXN];
vector<int> nid;
//queue<int> sajz;
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, int id){
	
	for(auto u : G[v])
		if(u != p) dfs_push(u, v, id);
	
	if((int)G[v].size() == 1) Q[id].push(v);

}


void compute(int u, int v){
	int id = 0;
	while(u != v){
		
		for(auto w : G[parent[u]]){
			if(w == u || w == parent[parent[u]]) continue;
			//sajz = std::queue<int>();
			nid.push_back(id);
			dfs_push(w, parent[u], id++);
			//Q.push_back(sajz);
		}
		
		u = parent[u];
	}

}

bool cmp(int a, int b){
	return (int)Q[a].size() > (int)Q[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(nid.begin(), nid.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 : nid){
		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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -