Codeforces911F Tree Destruction

未分类

首先距离一个点最远的点一定是直径上的某个端点。由此可以获得一个贪心策略：优先删除不在直径上的点，然后删除在直径上的点就行了。

#include <iostream>
#include <cstdio>
#include <vector>
typedef long long LL;
const int MAXN = 2e5;
int n, edge, ans1, lu, lv;
int f[MAXN | 1], fst[MAXN | 1], depth[MAXN | 1], father[MAXN | 1];
int calc[MAXN][2];
bool vis[MAXN | 1], flag[MAXN | 1];
LL ans;
int dp[MAXN | 1];
std::vector < int > vec[2];
struct Edge {
  int to, nxt;
  Edge() : to(0), nxt(0) {}
  Edge(int a, int b) : to(b), nxt(fst[a]) {}
} e[MAXN << 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void add_edge(int x, int y) {
  e[++edge] = Edge(x, y);
  fst[x] = edge;
}
void dfs1(int x, int fa) {
  father[x] = fa;
  depth[x] = depth[fa] + 1;
  dp[x] = 1;
  f[x] = x;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == fa) continue;
    dfs1(to, x);
    if (dp[to] + dp[x] > ans) {
      ans = dp[x] + dp[to];
      lu = f[x];
      lv = f[to];
    }
    if (dp[to] + 1 > dp[x]) {
      dp[x] = dp[to] + 1;
      f[x] = f[to];
    }
  }
}
void dfs2(int x, int dis, int fa, int from) {
  if (!vis[x]) {
    if (dis > calc[x][0]) {
      calc[x][0] = dis;
      calc[x][1] = from;
    }
    if (from == lv) ans += calc[x][0];
  }
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == fa) continue;
    dfs2(to, dis + 1, x, from);
  }
}
void dfs3(int x) {
  flag[x] = 1;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (vis[to] || flag[to]) continue;
    dfs3(to);
  }
  if (!vis[x]) {
    printf("%d %d %d\n", x, calc[x][1], x);
  }
}
int main() {
  n = read();
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs1(1, 0);  
  ans = ans * (ans - 1) / 2;
  int tx = lu, ty = lv;
  if (depth[tx] < depth[ty]) std::swap(tx, ty);
  while (depth[tx] > depth[ty]) vis[tx] = 1, vec[0].push_back(tx), tx = father[tx];
  while (tx != ty) vis[tx] = 1, vis[ty] = 1, vec[0].push_back(tx), vec[1].push_back(ty), tx = father[tx], ty = father[ty];
  vis[tx] = 1;
  vec[0].push_back(tx);
  for (int i = vec[1].size() - 1; i >= 0; --i) vec[0].push_back(vec[1][i]);
  vec[1].clear();
  dfs2(lu, 0, 0, lu);
  dfs2(lv, 0, 0, lv);
  printf("%lld\n", ans);
  for (std::vector < int > :: iterator it = vec[0].begin(); it != vec[0].end(); ++it) {
    int now = *it;
    dfs3(now);
  }
  for (int i = 0; i < vec[0].size() - 1; ++i) {
    printf("%d %d %d\n", vec[0][i], vec[0][vec[0].size() - 1], vec[0][i]);
  }
  return 0;
}