제출 #137080

#제출 시각아이디문제언어결과실행 시간메모리
137080silxikysNetwork (BOI15_net)C++14
0 / 100
13 ms12024 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 5e5+5; int n; vector<int> adj[maxn]; int deg[maxn]; int subtree[maxn]; void dfs(int i, int p, int label) { subtree[i] = label; for (int j: adj[i]) { if (j == p) continue; dfs(j,i,label); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; ++deg[a]; ++deg[b]; adj[a].push_back(b); adj[b].push_back(a); } vector<int> leafs; int start = 1; for (int i = 1; i <= n; i++) { if (deg[i] == 1) leafs.push_back(i); if (deg[i] > 1) { start = i; } } for (int j: adj[start]) { dfs(j,j,j); } sort(leafs.begin(),leafs.end(),[](auto a, auto b) { return subtree[a] < subtree[b]; }); vector<pair<int,int>> ans; int l = 0, r = leafs.size()-1; while (l <= r) { if (l == r) { ans.push_back({leafs[l],leafs[l+1]}); } else { ans.push_back({leafs[l],leafs[r]}); } l++; r--; } //output cout << ans.size() << '\n'; for (auto p: ans) { cout << p.first << ' ' << p.second << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...