Submission #1225209

#TimeUsernameProblemLanguageResultExecution timeMemory
1225209jellybeanNetwork (BOI15_net)C++20
100 / 100
198 ms44564 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define dd(x) cout<<#x<<" is "<<x<<endl; #define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl; #define dl(x) cout<<#x<<" is "<<endl; for(auto i:x) cout<<i<<' '; cout<<endl; #define fi first #define se second typedef pair<int,int> pii; const int N = 5e5+5; vector<int>adj[N]; int st[N]; int cnt = 1; void dfs(int x, int p){ st[x] = cnt++; for(auto i: adj[x]){ if(i == p) continue; dfs(i,x); } } bool cmp(int a, int b){ return st[a] < st[b]; } 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); } int d = 0, root = -1; vector<int>leaves; for(int i=1; i<=n; i++) { if(adj[i].size() == 1) d++, leaves.pb(i); else root = i; } dfs(root,-1); sort(leaves.begin(), leaves.end(), cmp); cout<<(d+1)/2<<'\n'; for(int i=0; i<(d+1)/2; i++){ cout<<leaves[i]<<' '<<leaves[i+(d/2)]<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...