Submission #30470

#TimeUsernameProblemLanguageResultExecution timeMemory
30470sampritiNetwork (BOI15_net)C++14
63 / 100
509 ms32100 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int> G[500001]; vector<int> leaves; void dfs(int i, int p) { bool leaf = true; for(int u: G[i]) { if(u == p) continue; leaf = false; dfs(u, i); } if(leaf) leaves.push_back(i); } int main() { ios::sync_with_stdio(false); cin.tie(0); 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); if(G[1].size() == 1) leaves.push_back(1); int ans = (leaves.size() + 1)/2; cout << ans << endl; for(int i = 0; i < ans; i++) { cout << leaves[i] << " " << leaves[i + leaves.size()/2] << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...