#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _322ZVFH ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
struct treelca{
int n;
int timer=0;
vec(vi) adj;
vi tin,tout,tour,tourid;
vi segtree;
vi depth;
treelca(int m,int root,vec(vi) neadj){
init(m,root,neadj);
}
void init(int m,int root,vec(vi) neadj){
n=m;
tin.clear();
tout.clear();
tour.clear();
tourid.clear();
depth.clear();
tin.resize(n,0);
tout.resize(n,0);
tourid.resize(n,0);
depth.resize(n,0);
adj=neadj;
dfs(root,-1);
segtree.resize(4*sz(tour));
build(1,0,sz(tour)-1);
}
void dfs(int v,int par){
tour.pb(v);
tourid[v]=sz(tour)-1;
tin[v]=timer++;
for(auto u : adj[v]){
if(u==par) continue;
depth[u]=depth[v]+1;
dfs(u,v);
tour.pb(v);
}
tout[v]=timer++;
}
void build(int node,int l,int r){
if(l==r){
segtree[node]=tour[l];
}else{
int m=(l+r)>>1;
build(node*2,l,m);
build(node*2+1,m+1,r);
segtree[node]=(tin[segtree[node*2]]<tin[segtree[node*2+1]]?segtree[node*2]:segtree[node*2+1]);
}
}
int query(int node,int l,int r,int _l,int _r){
if(l>_r or r<_l) return -1;
if(l>=_l and r<=_r) return segtree[node];
int m=(l+r)>>1;
int vl=query(node*2,l,m,_l,_r);
int vr=query(node*2+1,m+1,r,_l,_r);
if(min(vl,vr)==-1) return max(vl,vr);
return (tin[vl]<tin[vr]?vl:vr);
}
int ancestor(int from,int to){
int tinfrom=tin[from],tinto=tin[to];
if(tinfrom>tinto) swap(tinfrom,tinto);
return query(1,0,sz(tour)-1,tinfrom,tinto);
}
int dist(int u,int v){
return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
}
};
int main(){
_322ZVFH;
int n;
cin>>n;
vec(vi) adj(n);
rep(i,n-1){
int u,v;
cin>>u>>v;
u--,v--;
adj[u].pb(v);
adj[v].pb(u);
}
assert(n<=2000);
vi chs(n,0);
auto dfs=[&](auto self,int v,int par)->void{
chs[v]=1;
for(auto u : adj[v]){
if(u!=par){
self(self,u,v);
chs[v]+=chs[u];
}
}
};
dfs(dfs,0,-1);
treelca lca(n,0,adj);
int ans=1e9;
rep(v,n){
crep(u,v+1,n){
int up=lca.ancestor(u,v);
vi candies;
int l=chs[v],r=chs[u];
if(up==v or up==u){
if(l>r) swap(l,r);
candies={l,r-l,n-r};
ans=min(ans,*max_element(all(candies))-*min_element(all(candies)));
}else{
candies={l,r,n-l-r};
ans=min(ans,max({r-l,l-r,n-l-r-l,n-l-r-r}));
}
}
}
cout<<ans<<"\n";
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
364 KB |
Output is correct |
| 6 |
Correct |
393 ms |
880 KB |
Output is correct |
| 7 |
Correct |
431 ms |
864 KB |
Output is correct |
| 8 |
Correct |
409 ms |
884 KB |
Output is correct |
| 9 |
Correct |
384 ms |
876 KB |
Output is correct |
| 10 |
Incorrect |
429 ms |
864 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
364 KB |
Output is correct |
| 6 |
Correct |
393 ms |
880 KB |
Output is correct |
| 7 |
Correct |
431 ms |
864 KB |
Output is correct |
| 8 |
Correct |
409 ms |
884 KB |
Output is correct |
| 9 |
Correct |
384 ms |
876 KB |
Output is correct |
| 10 |
Incorrect |
429 ms |
864 KB |
Output isn't correct |
