#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <int n> struct MergeSortTree {
vi s[2*n] = {};
void buildFullTree() {
for (int i = n-1; i > 0; i--) {
s[i].resize(sz(s[i<<1]) + sz(s[i<<1|1]));
merge(all(s[i<<1]), all(s[i<<1|1]), s[i].begin());
}
}
int get_closer(int a, int b, int k) {
if (abs(k-a) < abs(k-b)) return a;
return b;
}
int find_close(int node, int k) {
auto iter = lower_bound(all(s[node]), k);
if(iter==s[node].end()) return *prev(iter);
return get_closer(*prev(iter), *iter, k);
}
int closest(int l, int r, int k) {
int output = -9999999;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) output = get_closer(output, find_close(l++, k), k);
if (r&1) output = get_closer(output, find_close(--r, k), k);
}
return output;
}
};
int N;
vi adj[200005];
int tin[200005], tout[200005];
MergeSortTree<200005> tree;
int timer = 0;
int dfs(int u, int p) {
tin[u] = timer++;
int subsz = 1;
for (int v : adj[u]) if (v != p) subsz += dfs(v, u);
tree.s[200005+tin[u]].emplace_back(subsz);
tout[u] = timer;
return subsz;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N; FOR(i, 0, N-1) {
int x, y; cin >> x >> y; x--; y--;
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
dfs(0, -1);
tree.buildFullTree();
int mn = 9999999;
FOR(i, 0, N) {
int X = tree.s[200005+i][0];
int optY = (N-X)/2;
int y = -9999999;
if (tin[i] > 0) y = tree.closest(0, tin[i], optY);
if (tout[i] < N) y = tree.get_closer(y, tree.closest(tout[i], N, optY), optY);
mn = min(mn, max(max(X, y), N-X-y) - min(min(X, y), N-X-y));
}
cout << mn;
}
Compilation message
Compilation timeout while compiling papricice
