#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,v[400005],nxt[400005],h[200005],tot,sz[200005],mn[200005],st[800005],dfn[200005],dfo[200005],T;
multiset<int> s1,s2;
bool ok;
void addedge(int x,int y){
v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}
void dfs1(int x,int fa){
dfn[x]=++T;
sz[x]=1;
for(int p=h[x];p;p=nxt[p]){
if(v[p]!=fa){
dfs1(v[p],x);
sz[x]+=sz[v[p]];
}
}
dfo[x]=T;
mn[sz[x]]=min(mn[sz[x]],dfo[x]);
}
void build(int id,int l,int r){
if(l==r) return (void)(st[id]=mn[l]);
int mid=(l+r)/2;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
st[id]=min(st[id<<1],st[id<<1|1]);
}
int query(int id,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return st[id];
int mid=(l+r)/2;
if(qr<=mid) return query(id<<1,l,mid,ql,qr);
else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
else return min(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
}
void dfs2(int x,int fa,int d){
/*
//sz[x]-d<=n-t<=sz[x]+d
//n-sz[x]-d<=t<=n-sz[x]+d
//sz[x]-d<=t-sz[x]<=sz[x]+d
//2*sz[x]-d<=t<=2*sz[x]+d
//n-t-d<=t-sz[x]<=n-t+d
//n-d+sz[x]<=2*t<=n+d+sz[x]
//sz[x]-d<=t<=sz[x]+d
//2*sz[x]-d<=n-t-sz[x]<=sz[x]+d
//n-d-2*sz[x]<=t<=n+d-2*sz[x]
//n-sz[x]-d<=2*t<=n-sz[x]+d
*/
int L=max({n-sz[x]-d,2*sz[x]-d,(n-d+sz[x]+1)/2});
int R=min({n-sz[x]+d,2*sz[x]+d,(n+d+sz[x])/2});
auto it=s2.lower_bound(L);
if(it!=s2.end()&&*it<=R) ok=true;
s2.insert(sz[x]);
L=max({sz[x]-d,n-d-2*sz[x],(n-sz[x]-d+1)/2});
R=min({sz[x]+d,n+d-2*sz[x],(n-sz[x]+d)/2});
L=max(1,L); R=min(R,n);
if(L<=R&&query(1,1,n,L,R)<dfn[x]) ok=true;
for(int p=h[x];p;p=nxt[p]){
if(v[p]!=fa){
dfs2(v[p],x,d);
}
}
s2.erase(s2.find(sz[x]));
s1.insert(sz[x]);
}
bool check(int d){
s1.clear();
s2.clear();
ok=false;
dfs2(1,1,d);
return ok;
}
int main(){
n=readint();
for(int i=1;i<n;i++) addedge(readint(),readint());
for(int i=1;i<=n;i++) mn[i]=1e9;
dfs1(1,1);
build(1,1,n);
int l=0,r=n,ans=n;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
printf("%d\n",ans);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
4 ms |
4704 KB |
Output is correct |
7 |
Correct |
5 ms |
4700 KB |
Output is correct |
8 |
Correct |
4 ms |
4708 KB |
Output is correct |
9 |
Correct |
4 ms |
4700 KB |
Output is correct |
10 |
Correct |
5 ms |
4704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
4 ms |
4704 KB |
Output is correct |
7 |
Correct |
5 ms |
4700 KB |
Output is correct |
8 |
Correct |
4 ms |
4708 KB |
Output is correct |
9 |
Correct |
4 ms |
4700 KB |
Output is correct |
10 |
Correct |
5 ms |
4704 KB |
Output is correct |
11 |
Execution timed out |
1026 ms |
20448 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |