Submission #394605

#TimeUsernameProblemLanguageResultExecution timeMemory
394605minoumNetwork (BOI15_net)C++17
0 / 100
7 ms11984 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const int MAXN = 5e5+10; int n, st[MAXN], tim = 0, r = -1,lfc = 0; vector <int> adj[MAXN]; vector <pair<int,int>> ans; void dfs(int v, int parv){ st[v] = tim; tim++; if((int)adj[v].size()==1) ans.push_back({st[v],v}); for(int u: adj[v]) if(u!=parv) dfs(u,v); return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n-1; i++){ int u,v; cin >> u >> v; u--; v--; adj[v].push_back(u); adj[u].push_back(v); } for(int i = 0; i < n; i++) lfc += ((int)adj[i].size()==1); for(int i = 0; i < n; i++) if((int)adj[i].size()>1){ r = i; break; } if(n==2){ cout << 1 << '\n' << "1 2" << '\n'; return 0; } dfs(r,-1); sort(ans.begin(), ans.end()); cout << ((lfc+1)/2) << '\n'; if(lfc&1){ cout << r+1 << " " << ans.back().second+1 << '\n'; ans.pop_back(); } lfc = (int)ans.size()/2; for(int i = 0; i < lfc; i++) cout << ans[i].second+1 << " " << ans[i+lfc].second+1 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...