1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include<bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define drp(i,j,k) for(int i=(j);i>=(k);--i)
using namespace std;
inline int read(){
int x=0,f=0;char ch;
while(!isdigit(ch=getchar())) f|=ch=='-';
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
inline int max3(int x,int y,int z){return max(max(x,y),z);}
inline int min3(int x,int y,int z){return min(min(x,y),z);}
inline int jc3(int x,int y,int z){return max3(x,y,z)-min3(x,y,z);}
//------------------------------------------------------//
const int N=2e5+5;
int n,ans=N;
int fir[N],nex[N<<1],to[N<<1],pos;
void add(int x,int y){
to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
std::swap(x,y);
to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
}
int siz[N],dep[N],fa[N][21];
int leaf[N],cnt;
void dfs1(int u,int f){
dep[u]=dep[fa[u][0]=f]+1;siz[u]=1;
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
}
if(siz[u]==1) leaf[++cnt]=u;
}
int lca(int x,int y){
if(dep[x]<dep[y]) std::swap(x,y);
drp(i,17,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
drp(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return x==y?x:fa[x][0];
}
int w(int x,int y){
int z=lca(x,y);
if(x==z||y==z){
if(dep[x]<dep[y]) std::swap(x,y);
return jc3(siz[x],siz[z]-siz[x],n-siz[z]);
}
else return jc3(siz[x],siz[y],n-siz[x]-siz[y]);
}
void find(int root,int k){
if(ans!=N&&n<=2000) return ;
dfs1(root,0);
rep(i,1,17) rep(u,1,n)
fa[u][i]=fa[fa[u][i-1]][i-1];
if(n<=2000){
if(ans!=N) return;
rep(i,1,n) rep(j,1,n)
ans=std::min(ans,w(i,j));
return ;
}
int tim=40;
while(tim--){
int x,y;
if(tim&1) {
x=leaf[rand()%cnt+1];
y=leaf[rand()%cnt+1];
}
else {
x=rand()%n+1;
y=rand()%n+1;
}
bool con=true;
int now=w(x,y);
while(con) {
con=false;
drp(i,k,0) if(fa[x][i]) {
int ne=w(fa[x][i],y);
if(ne>now) continue;
x=fa[x][i]; now=ne;
con=true;
}
if(!con) {
std::swap(x,y);
drp(i,0,0) if(fa[x][i]) {
int ne=w(fa[x][i],y);
if(ne>now) continue;
x=fa[x][i]; now=ne;
con=true;
}
}
if(rand()&1)std::swap(x,y);
}
ans=std::min(ans,now);
}
}
signed main(){
srand(time(0));
freopen("papricice.in","r",stdin);
freopen("papricice.out","w",stdout);
n=read();
rep(i,1,n-1) add(read(),read());
rep(i,1,5) find(rand()%n+1,i),cnt=0;
printf("%lld\n",ans);
} |
Chip’s starting cell is green, the only cell from which chip can’t move is red. if the chip is in the yellow cell, then blue cells are all options to move the chip in one move.
