复习搞高版

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define not !
#define and &&
#define or ||

#define r() fast_read()
#define rep(inc, frm, to) for (size_t inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (int inc = frm; inc > (to); --inc)

#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, -1) printf("%d%c", getbit(x, i), i ? 0 : 10); }

#define oo 0x7fffffff

#define MAX_N 100010

typedef long long int ll;

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (c < 48 or c > 57) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (c >= 48 and c <= 57) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
  int to, nxt;
} edges[MAX_N << 1];

void addEdge(int u, int v) {
  edges[++edge_cnt] = (Edge) {v, head[u]};
  head[u] = edge_cnt;
}

void print_graph(const int n) {
  rep(u, 1, n + 1) {
    printf("Vertex %ld --> ", u);
    for (int e = *(head + u); e; e = (edges + e)->nxt)
      printf("[%d]\t", (edges + e)->to);
    putchar(10);
  }
}

int n, ans = oo;

int DFS(int u, int p) {
  int tot = 1, max_sz = 0;
  for (int e = *(head + u), to; e; e = (edges + e)->nxt) {
    to = (edges + e)->to;
    if (to == p) continue;
    int sz = DFS(to, u);
    tot += sz;
    max_sz = fmax(max_sz, sz);
  }
  ans = fmin(ans, fmax(max_sz, n - tot));
  return tot;
}

signed main(int argc, char const *argv[]) {
  n = r();
  int u, v;
  rep(i, 0, n - 1) {
    u = r(), v = r();
    addEdge(u, v), addEdge(v, u);
  }
  // print_graph(n);
  DFS(1, 0);
  printf("%d\n", ans);
  return ~~(0 ^ 0);
}

树形DP + DFS

#include <iostream>
#include <vector>

using namespace std;
int n, u, v;

// depth first search algorithm
int dfs(vector<vector<int>>& g,
        vector<int>& counts, int cur, int parent) {

  int total = 1;
  for (const auto& nei : g[cur]) {
    if (nei == parent) continue; // 勇往向前，不走回头路 ！！

    int cnt = dfs(g, counts, nei, cur); // 一个子连通分量（分叉）返回的节点数量！
    counts[cur] = max(counts[cur], cnt);
    total += cnt;
  }

  counts[cur] = max(counts[cur], n - total);
  return total;
}

int main(void) {
  scanf("%d", &n);
  vector<vector<int>> g(n + 1);
  vector<int> counts(n + 1);
  // build thd undirected graph
  for (int i = 0; i < n - 1; ++i) {
    scanf("%d %d", &u, &v);
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  dfs(g, counts, 1, 0);

  int ans = 1; // ans == 树的重心
  for (int i = 2; i <= n; ++i)
    if (counts[i] < counts[ans]) ans = i;

  return printf("%d\n", counts[ans]), 0;
}