#include <bits/stdc++.h>
using namespace std;
void tarjan(int u, int p, vector<vector<int>> &adj, vector<int> &tin, vector<int> &low, vector<bool> &vis, int &timer, bool &is_bridge) {
vis[u] = true;
tin[u] = low[u] = timer++;
for (auto &v : adj[u]) {
if (v == p) continue;
if (vis[v]) {
low[u] = min(low[u], tin[v]);
continue;
}
tarjan(v, u, adj, tin, low, vis, timer, is_bridge);
low[u] = min(low[u], low[v]);
is_bridge = is_bridge || (low[v] > tin[u]);
}
}
bool has_bridge(vector<vector<bool>> &adjmat) {
int n = adjmat.size();
vector<vector<int>> adj(n, vector<int>());
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (adjmat[i][j] != 1) continue;
adj[i].push_back(j);
adj[j].push_back(i);
}
}
vector<int> tin(n, -1); vector<int> low(n, -1); vector<bool> vis(n, false); int timer = 0; bool is_bridge = false;
tarjan(0, 0, adj, tin, low, vis, timer, is_bridge);
return is_bridge;
}
int n;
vector<vector<int>> adj; vector<pair<int, int>> edges;
vector<int> sz, leaves;
void get_subtree_size(int u, int p) {
sz[u] = 1;
for (auto &v : adj[u]) {
if (v == p) continue;
get_subtree_size(v, u);
sz[u] += sz[v];
}
if (sz[u] == 1 && p != -1) leaves.push_back(u);
}
int find_centroid(int u, int p) {
for (auto &v : adj[u]) {
if (v == p) continue;
if (sz[v] * 2 > n) return find_centroid(v, u);
}
return u;
}
uint64_t next_subset(uint64_t x) {
uint64_t c = x & -x;
uint64_t r = x + c;
return (((r ^ x) >> 2) / c) | r;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
adj.assign(n, vector<int>()); sz.assign(n, -1);
for (int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
edges.push_back({u, v});
}
get_subtree_size(0, -1);
int centre = find_centroid(0, -1);
leaves.clear(); get_subtree_size(centre, -1);
int n_edges = int(leaves.size() - 1) * int(leaves.size()) / 2;
int best_mask = 0;
for (int k = 1; k <= n_edges; k++) {
int mask = (1 << k) - 1;
while (mask < (1 << n_edges)) {
vector<vector<bool>> adjmat(n, vector<bool>(n, false));
for (auto &el : edges) adjmat[el.first][el.second] = adjmat[el.second][el.first] = true;
int cur_bit = 0;
for (int i = 0; i < leaves.size(); i++) {
for (int j = i + 1; j < leaves.size(); j++) {
adjmat[leaves[i]][leaves[j]] = adjmat[leaves[j]][leaves[i]] = mask & (1 << cur_bit);
cur_bit++;
}
}
if (!has_bridge(adjmat)) {
best_mask = mask;
break;
}
mask = next_subset(mask);
}
if (best_mask != 0) break;
}
vector<pair<int, int>> new_edges;
int cur_bit = 0;
for (int i = 0; i < leaves.size(); i++) {
for (int j = i + 1; j < leaves.size(); j++) {
if (best_mask & (1 << cur_bit)) {
new_edges.push_back({leaves[i]+1, leaves[j]+1});
}
cur_bit++;
}
}
cout << new_edges.size() << "\n";
for (auto &el : new_edges) {
cout << el.first << " " << el.second << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |