제출 #1117766

#제출 시각아이디문제언어결과실행 시간메모리
1117766PwoNetwork (BOI15_net)C++17
0 / 100
3 ms12880 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n, depth[500005], par[500005]; vector<int> g[500005]; void dfs(int v, int p) { depth[v] = depth[p] + 1; par[v] = p; for (const int u : g[v]) { if (u != p) dfs(u, v); } } int32_t main() { cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 1); int mx = 0, node = 0; for (int i = 1; i <= n; i++) { if (depth[i] > mx) mx = depth[i], node = i; } fill(depth, depth + n + 1, 0); dfs(node, node); mx = 0; int node2 = 0; for (int i = 1; i <= n; i++) { if (depth[i] > mx) mx = depth[i], node2 = i; } par[node] = -1; set<int> st; int cur = node2; while (cur != -1) { st.insert(cur); cur = par[cur]; } cout << n - mx << '\n'; for (int i = 1; i <= n; i++) { if (st.find(i) == st.end()) cout << i << ' ' << node << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...