牛客小bai月赛39 F 孤独（dp）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans = INT_MAX, n;
int sz[1000006];
int dp[1000006];
vector<int>vec[1000006];
void dfs(int i, int fa) {
  sz[i] = 1;
  int mx1 = 0;
  int mx2 = 0;
  int mx3 = 0; //第三大的子树
  for (auto j : vec[i]) {
    if (j == fa)continue;
    dfs(j, i);
    sz[i] += sz[j];
    if (sz[j] > sz[mx1]) {
      mx3 = mx2;
      mx2 = mx1;
      mx1 = j;
    } else if (sz[j] > sz[mx2]) {
      mx3 = mx2;
      mx2 = j;
    } else if (sz[j] > sz[mx3]) {
      mx3 = j;
    }
    dp[i] = max(dp[mx1], sz[mx2]);
  }
  ans = min(ans, max(n - sz[i], max(dp[mx1], max(dp[mx2], sz[mx3]))));
}
int main() {
  int i, j, x, y;
  scanf("%d", &n);
  for (i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    vec[x].push_back(y);
    vec[y].push_back(x);
  }
  dfs(1, 0);
  printf("%d\n", ans);
  return 0;
}