Submission #1270650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270650		lmduc270410	Network (BOI15_net)	C++20	100 / 100	249 ms	51728 KiB

net

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 1e6 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

int n, in[N], h[N];
vector<int> adj[N], v;
int d[N];

void dfs(int u, int par){
	if(in[u] == 1) v.push_back(u);
	for(int v : adj[u]){
		if(v == par) continue;
		dfs(v, u);
	}
}

bool comp(int x, int y){
	return h[x] > h[y];
}

void solve(){
	
	cin>>n;
	for(int i = 1; i < n; i++){
		int x, y; cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
		in[x]++; in[y]++;
	}

	dfs(1, 0);
    int k = ((int)v.size() + 1) / 2;
    
    // for(int x : v) cout<<x<<" ";
    // cout<<'\n';
	// cout<<k<<'\n';

	cout<<k<<'\n';
	for(int i = 0; i < k; i++){
		cout<<v[i]<<" "<<v[(i + k) % ((int)v.size())]<<'\n';
	}
	// if((int)v.size() % 2 == 1) cout<<v.back()<<" "<<1<<'\n';
}

signed main(){
	
	// freopen(".inp", "r", stdin);
	// freopen(".out", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int tc = 1;
	// cin>>tc;
	while(tc--) solve();
}

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