#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 4e5+1;
const int inf = 1e18;
vi sz(N),best(N),edges[N],tin(N),tout(N),tour = {0};
vi t[4*N];
int timer = 1;
int dfs(int node,int parent) {
tour.pb(node);
tin[node] = timer++;
int ans = 1;
for (auto nb : edges[node]) {
if (nb != parent) ans+=dfs(nb,node);
}
tout[node] = timer++;
tour.pb(node);
return sz[node] = ans;
}
vi merge(vi&a ,vi& b) {
int ptr = 0,ptr2 = 0;
vi v;
int n = a.size();
int m = b.size();
while (ptr < n && ptr2 < m) {
if (a[ptr] < b[ptr2]) v.pb(a[ptr++]);
else v.pb(b[ptr2++]);
}
while (ptr < n) v.pb(a[ptr++]);
while (ptr2 < m) v.pb(b[ptr2++]);
return v;
}
void build(int node,int l,int r) {
if (l == r) {
t[node].pb(sz[tour[l]]);
return;
}
int m = (l+r) >> 1;
build(2*node,l,m);
build(2*node+1,m+1,r);
t[node] = merge(t[2*node],t[2*node+1]);
}
pair<int,int> query(int node,int l,int r,int L,int R,double x) {
if (l > R || r < L) return {inf,-inf};
if (l >= L && r <= R){
int x1=inf,x2=inf;
auto it = lower_bound(t[node].begin(),t[node].end(),x);
if(it!=t[node].end()) x2 =*it;
if (it != t[node].begin()) x1 = *prev(it);
if (abs(x-x1) < abs(x-x2)) return {abs(x-x1),x1};
else return {abs(x-x2),x2};
}
int m = (l+r) >> 1;
return min(query(2*node,l,m,L,R,x),query(2*node+1,m+1,r,L,R,x));
}
void solve() {
int n;
cin >> n;
for (int i=1;i<=n-1;i++) {
int a,b;
cin >> a >> b;
edges[a].pb(b);
edges[b].pb(a);
}
dfs(1,1);
int m = tour.size()-1;
build(1,1,m);
int best = inf;
for (int i=1;i<=n;i++) {
//cout << "Node" sp i sp ":";
int l = tin[i];
int r = tout[i];
pair<int,int> h = min(query(1,1,n,1,l-1,(n-sz[i])/2.0),
query(1,1,n,r+1,m,(n-sz[i])/2.0));
int h1 = h.second;
int h2 = n-sz[i]-h1;
int h3 = sz[i];
int v =max({h1,h2,h3})-min({h1,h2,h3});
//cout << v << " ";
h = query(1,1,n,l+1,r-1,(sz[i]/2.0));
h1 = h.second;
h2 = sz[i]-h1;
h3 = n-sz[i];
v = max({h1,h2,h3})-min({h1,h2,h3});
//cout << v << endl;
best = min(best,v);
}
cout << best << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
59996 KB |
Output is correct |
| 2 |
Correct |
15 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
59972 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
59996 KB |
Output is correct |
| 2 |
Correct |
15 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
59972 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
59996 KB |
Output is correct |
| 2 |
Correct |
15 ms |
59996 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
59972 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
