Submission #1189169

#TimeUsernameProblemLanguageResultExecution timeMemory
1189169njoopNetwork (BOI15_net)C++17
100 / 100
185 ms45536 KiB
#include <bits/extc++.h> using namespace std; typedef long long ll; vector<int> g[500010], leaves; void dfs(int no, int pa) { if(g[no].size() == 1) { leaves.push_back(no); } for(auto i: g[no]) { if(i == pa) continue; dfs(i, no); } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } dfs(1, 0); int l=leaves.size(); int m=l/2; vector<pair<int,int>> ans; for(int i=0;i<m;i++){ ans.emplace_back(leaves[i], leaves[i+m]); } if(l%2){ ans.emplace_back(leaves[0], leaves[l-1]); } cout<<ans.size()<<"\n"; for(auto &p: ans){ cout<<p.first<<" "<<p.second<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...