#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define ALL(x) (x).begin(), (x).end()
#define isz(x) int((x).size())
static const int MAXN = 200000;
int n;
vector<int> adj[MAXN+1], children[MAXN+1];
int parentArr[MAXN+1];
int sz[MAXN+1];
int stk[MAXN+1], ord[MAXN+1], ordsz;
void solve(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
FOR(i,1,n) {
adj[i].clear();
children[i].clear();
}
FOR(i,1,n-1){
int x,y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
// -- dựng parent + thứ tự post-order không đệ quy --
ordsz = 0;
int top = 0;
stk[top++] = 1;
parentArr[1] = 0;
// first: tạo thứ tự preorder lưu vào ord
while(top){
int u = stk[--top];
ord[ordsz++] = u;
for(int v: adj[u]){
if(v == parentArr[u]) continue;
parentArr[v] = u;
stk[top++] = v;
children[u].push_back(v);
}
}
// rồi duyệt ngược ord để tính sz[u]
FORD(idx, ordsz-1, 0){
int u = ord[idx];
sz[u] = 1;
for(int v: children[u]){
sz[u] += sz[v];
}
}
ll best = LLONG_MAX;
// xét mỗi nút u
FOR(u,1,n){
// gom các kích thước "nhánh" quanh u
vector<int> vals;
vals.reserve(1 + children[u].size());
// nhánh lên trên nếu có
if(parentArr[u] != 0){
vals.push_back(n - sz[u]);
}
// nhánh mỗi con v
for(int v: children[u]){
vals.push_back(sz[v]);
}
int m = isz(vals);
if(m < 2) continue;
sort(ALL(vals));
// với mỗi i, tìm j>i sao cho vals[j] gần target = 2n/3 - vals[i]
for(int i = 0; i < m; ++i){
ll a = vals[i];
ll target = (2LL*n)/3 - a;
// tìm vị trí lower_bound trong phần [i+1..m)
int lo = i+1, hi = m-1, pos = m;
while(lo <= hi){
int mid = (lo+hi)/2;
if(vals[mid] >= target){
pos = mid;
hi = mid-1;
} else lo = mid+1;
}
// kiểm tra vài ứng viên quanh pos
for(int j = max(i+1, pos-1); j <= min(m-1, pos+1); ++j){
if(j <= i) continue;
ll b = vals[j];
ll c = n - a - b;
ll mn = min(a, min(b, c));
ll mx = max(a, max(b, c));
best = min(best, mx - mn);
}
}
}
cout << best << "\n";
}
int main(){
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |