#include <bits/stdc++.h>
#define PB push_back
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 200100;
const int oo = 2e9;
vector<int> g[N];
int tt = 1, n, tin[N], tout[N], siz[N], ms[N];
int ans = oo, glob = -1;
void dfs(int v, int p){
tin[v] = tt++;
siz[v] = 1;
for (int u : g[v]){
if (u == p) continue;
dfs(u, v);
siz[v] += siz[u];
}
ms[tin[v]] = siz[v];
tout[v] = tt - 1;
}
struct seg_tree{
seg_tree *l, *r;
int sm;
seg_tree(): l(0), r(0), sm(0) {}
seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}
void build(int tl, int tr){
if (tl == tr) return;
l = new seg_tree();
r = new seg_tree();
int md = (tl + tr) >> 1;
l -> build(tl, md);
r -> build(md + 1, tr);
}
void update(int tl, int tr, int ps){
sm++;
if (tl == tr) return;
int md = (tl + tr) >> 1;
if (ps <= md) {
l = new seg_tree(l);
l -> update(tl, md, ps);
} else {
r = new seg_tree(r);
r -> update(md + 1, tr, ps);
}
}
};
seg_tree *pref[N];
seg_tree *suf[N];
seg_tree* get_rit(seg_tree *v){
if (!v)
return 0;
else return (v -> r);
}
seg_tree* get_lef(seg_tree *v){
if (!v)
return 0;
else return (v -> l);
}
int get_sum(seg_tree *v){
return (v ? v -> sm : 0);
}
void real_get_max(seg_tree *v1, seg_tree *v2, int tl, int tr){
if (tl == tr){
glob = tl;
return;
}
int md = (tl + tr) >> 1;
if (get_sum(get_rit(v1)) - get_sum(get_rit(v2)) > 0)
real_get_max(get_rit(v1), get_rit(v2), md + 1, tr);
else real_get_max(get_lef(v1), get_lef(v2), tl, md);
}
void real_get_min(seg_tree *v1, seg_tree *v2, int tl, int tr){
if (tl == tr){
glob = tl;
return;
}
int md = (tl + tr) >> 1;
if (get_sum(get_lef(v1)) - get_sum(get_lef(v2)) > 0)
real_get_min(get_lef(v1), get_lef(v2), tl, md);
else real_get_min(get_rit(v1), get_rit(v2), md + 1, tr);
}
void get_max(seg_tree *v1, seg_tree *v2, int tl, int tr, int ql, int qr){
if (ql > qr || glob != -1) return;
if (tl == ql && tr == qr){
if (get_sum(v1) - get_sum(v2) > 0)
real_get_max(v1, v2, tl, tr);
return;
}
int md = (tl + tr) >> 1;
get_max(get_rit(v1), get_rit(v2), md + 1, tr, max(md + 1, ql), qr);
get_max(get_lef(v1), get_lef(v2), tl, md, ql, min(qr, md));
}
void get_min(seg_tree *v1, seg_tree *v2, int tl, int tr, int ql, int qr){
if (ql > qr || glob != -1) return;
if (tl == ql && tr == qr){
if (get_sum(v1) - get_sum(v2) > 0)
real_get_min(v1, v2, tl, tr);
return;
}
int md = (tl + tr) >> 1;
get_min(get_lef(v1), get_lef(v2), tl, md, ql, min(qr, md));
get_min(get_rit(v1), get_rit(v2), md + 1, tr, max(md + 1, ql), qr);
}
void last_dfs(int v, int p){
for (int u : g[v]){
if (u == p) continue;
last_dfs(u, v);
}
if (siz[v] <= n - siz[v]){
int SZ = n - siz[v];
int SE = siz[v];
int bst = oo;
{
// <= SZ / 2
if (tin[v] > 1){
glob = -1;
get_max(pref[tin[v] - 1], NULL, 1, n, 1, SZ / 2);
if (glob != -1){
glob = SZ - glob;
if (abs(SE - glob) < abs(SE - bst))
bst = glob;
}
}
if (tout[v] < n){
glob = -1;
get_max(suf[tout[v] + 1], NULL, 1, n, 1, SZ / 2);
if (glob != -1){
glob = SZ - glob;
if (abs(SE - glob) < abs(SE - bst))
bst = glob;
}
}
}
{
// > SZ / 2
if (tin[v] > 1){
glob = -1;
get_min(pref[tin[v] - 1], NULL, 1, n, SZ / 2 + 1, n);
if (glob != -1){
if (abs(SE - glob) < abs(SE - bst))
bst = glob;
}
}
if (tout[v] < n){
glob = -1;
get_min(suf[tout[v] + 1], NULL, 1, n, SZ / 2 + 1, n);
if (glob != -1){
if (abs(SE - glob) < abs(SE - bst))
bst = glob;
}
}
}
ans = min(ans, abs(SE - bst));
}
if (n - siz[v] <= siz[v]){
int SZ = siz[v];
int SE = n - siz[v];
int bst = oo;
{
// <= SZ / 2
glob = -1;
get_max(pref[tout[v]], pref[tin[v] - 1], 1, n, 1, SZ / 2);
if (glob != -1){
glob = SZ - glob;
if (abs(SE - glob) < abs(SE - bst))
bst = glob;
}
}
{
// > SZ / 2
glob = -1;
get_min(pref[tout[v]], pref[tin[v] - 1], 1, n, SZ / 2 + 1, n);
if (glob != -1){
if (abs(SE - glob) < abs(SE - bst))
bst = glob;
}
}
ans = min(ans, abs(SE - bst));
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n;
for (int i = 1; i < n; i++){
int x, y; cin >> x >> y; x--; y--;
g[x].PB(y);
g[y].PB(x);
}
dfs(0, -1);
// build pref && suf
pref[0] = new seg_tree();
suf[n + 1] = new seg_tree();
pref[0] -> build(1, n);
suf[n + 1] -> build(1, n);
for (int i = 1; i <= n; i++){
pref[i] = new seg_tree(pref[i - 1]);
pref[i] -> update(1, n, ms[i]);
}
for (int i = n; i > 0; i--){
suf[i] = new seg_tree(suf[i + 1]);
suf[i] -> update(1, n, ms[i]);
}
last_dfs(0, -1);
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
