coci2021_r1_papricice.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 200005;

vector<int> adj[N];
int cnt[N], res = INT_MAX;
multiset<int> ms;

int cal(int x, int sum, int c, bool b = 0) {
  auto it = ms.lower_bound(x);
  if (b) {
    if (it == ms.begin()) return INT_MAX;
    it = prev(it);
  }
  if (it == ms.end()) return INT_MAX;
  return max({sum - *it, *it, c}) - min({sum - *it, *it, c});
}

void binsearch(int sum, int c) {
  int l = 0, r = sum, ans = INT_MAX;
  while (l <= r) {
    int x = (l + r) / 2;
    if (cal(x, sum, c, 1) >= cal(x, sum, c)) {
      l = x + 1;
      ans = x;
    }
    else r = x - 1;
  }
  res = min({res, cal(ans, sum, c), cal(ans + 1, sum, c)});
}

void dfs1(int i, int p) {
  cnt[i] = 1;
  for (auto &j : adj[i]) {
    if (j == p) continue;
    dfs1(j, i);
    cnt[i] += cnt[j];
  }
}

void dfs2(int i, int p, int sum) {
  sum += cnt[i];
  for (auto &j : adj[i]) {
    if (j == p) continue;
    sum -= cnt[j];
    ms.insert(sum);
    binsearch(sum, cnt[j]);
    dfs2(j, i, sum);
    ms.erase(ms.find(sum));
    sum += cnt[j];
  }
}

void dfs3(int i, int p) {
  for (auto &j : adj[i]) {
    if (j == p) continue;
    binsearch(cnt[1] - cnt[j], cnt[j]);
    dfs3(j, i);
  }
  ms.insert(cnt[i]);
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 0, 0);
  ms.clear();
  dfs3(1, 0);
  cout << res << '\n';
}