Submission #96949

#TimeUsernameProblemLanguageResultExecution timeMemory
96949dalgerokNetwork (BOI15_net)C++14
100 / 100
750 ms65728 KiB
#include<bits/stdc++.h> using namespace std; const int N = 5e5 + 5; int n, sz, a[N]; vector < int > g[N]; void dfs(int v, int pr = -1){ for(int to : g[v]){ if(to != pr){ dfs(to, v); } } if((int)g[v].size() == 1){ a[++sz] = v; } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; for(int i = 1; i < n; i++){ int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } int rt = -1; for(int i = 1; i <= n; i++){ if((int)g[i].size() > 1){ rt = i; } } dfs(rt); int ans = (sz + 1) / 2; cout << ans << "\n"; for(int i = 1; i < ans; i++){ cout << a[i] << " " << a[i + ans] << "\n"; } if(sz & 1){ cout << a[1] << " " << a[ans] << "\n"; } else{ cout << a[sz] << " " << a[ans]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...