danihao123's Blog

LibreOJ真是好用（以后尽可能少用BZOJ）

这题我觉得真是个意识流神题。

考虑所有度数为1的点（姑且称为叶子），这些点是一定要向外连边的（只要有一个度数为1的树边不在一个环中，肯定就出桥了）。

那是否可以只在这种叶子之间连边？答案是肯定的。假设叶子上形成了足够多的环，那么上面的边可以随便上。

那是否叶子配对连边就行了（这说明答案是\(\lceil \frac{l}{2}\rceil\)，其中\(l\)是叶子的数目）？答案也是肯定的。但这种方案里显然两个结点间有新边则两点不可能在根的同一棵子树里。

然后就有一种乱搞做法：找到一个根使得每个子树的叶子数都不超过总数的一半（这种点很显然存在），然后从这个根开始DFS，把所有叶子按照DFS序排序一遍，前一半向后一半依次连边。如果叶子数目是奇数，那么最后一个可以随便连。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <set>
#include <vector>
using std::vector;
const int maxn = 500005;
vector<int> G[maxn];

int n;
int leaves[maxn];
vector<int> L;
int leavenum = 0;
void calc_leave(int x, int fa = 0) {
  if(int(G[x].size()) == 1) {
    leaves[x] = 1; L.push_back(x);
    leavenum ++;
  }
  for(auto v : G[x]) {
    if(v != fa) {
      calc_leave(v, x);
      leaves[x] += leaves[v];
    }
  }
}
int gen_rt(int x, int fa = 0) {
  for(auto v : G[x]) {
    if(v != fa && leaves[v] * 2 >= leavenum) {
      return gen_rt(v, x);
    }
  }
  return x;
}
int dfn[maxn];
void calc_dfn(int x, int fa = 0) {
  static int cnt = 0;
  dfn[x] = ++ cnt;
  for(auto v : G[x]) {
    if(v != fa) {
      calc_dfn(v, x);
    }
  }
}

bool cmp(const int &x, const int &y) {
  return dfn[x] < dfn[y];
}
int main() {
  scanf("%d", &n);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  calc_leave(1);
  int rt = gen_rt(1);
  calc_dfn(rt);
  sort(L.begin(), L.end(), cmp);
  printf("%d\n", (leavenum + 1) / 2);
  int half = leavenum / 2;
  for(int i = 0; i < half; i ++) {
    printf("%d %d\n", L[i], L[i + half]);
  }
  if(1 & leavenum) {
    printf("%d %d\n", L[half - 1], L[leavenum - 1]);
  }
  return 0;
}