#include <bits/stdc++.h>
using namespace std;
int sz[200005];
vector<pair<int,int> > paths[200005];
int big[200005];
int big2[200005];
int hd[200005];
vector<int> adjl[200005];
int pa[200005][20];
void dfs(int node, int p){
pa[node][0] = p;
for (int x = 1; x<20; x++){
pa[node][x] = pa[pa[node][x-1]][x-1];
}
sz[node] = 1;
for (auto x : adjl[node]){
if (x==p) continue;
dfs(x,node);
sz[node] += sz[x];
}
}
void decomp(int node, int p, int head){
paths[head].push_back({-sz[node],node});
hd[node] = head;
int v1 = 0;
int v2 = 0;
big2[node] = -1; big[node] = -1;
for (auto x : adjl[node]){
if (x==p) continue;
if (sz[x]>v1){
v2 = v1;
big2[node] = big[node];
v1 = sz[x]; big[node] = x;
}
else if (sz[x]>v2){
v2 = sz[x];
big2[node] = x;
}
}
if (big[node]!=-1)decomp(big[node],node,head);
if (big2[node]!=-1)decomp(big2[node],node,big2[node]);
}
int n;
int getv(int a, int b){
return max(a,max(b,n-a-b))-min(a,min(b,n-a-b));
}
int check(int node){
//printf("checking %d\n",node);
if (hd[node]==1){
int remsize = n-sz[node];
int thing = remsize/2;
if (thing==0){
return 999999999;
}
int tt = lower_bound(paths[hd[node]].begin(),paths[hd[node]].end(),make_pair(-thing-sz[node]+1,-1))-paths[hd[node]].begin();
int splitnode = paths[hd[node]][tt-1].second;
//printf("split1 = %d\n",splitnode);
int t2 = -1;
if (big2[splitnode]!=-1) t2 = lower_bound(paths[big2[splitnode]].begin(),paths[big2[splitnode]].end(),make_pair(1-thing,-1))-paths[big2[splitnode]].begin();
if (t2==0) {
int ans = getv(sz[node],sz[splitnode]-sz[node]);
if (big[splitnode]!=-1 && big[splitnode]!=node)ans = min(ans,getv(sz[node],sz[big[splitnode]]-sz[node]));
if (big2[splitnode]!=-1) ans = min(ans,getv(sz[node],sz[big2[splitnode]]));
return ans;
}
if (t2==-1){
int ans = getv(sz[node],sz[splitnode]-sz[node]);
if (big[splitnode]!=-1 && big[splitnode]!=node)ans = min(ans,getv(sz[node],sz[big[splitnode]]-sz[node]));
return ans;
}
splitnode = paths[big2[splitnode]][t2-1].second;
//printf("split2 = %d\n",splitnode);
int ans = getv(sz[node],sz[splitnode]);
if (big[splitnode]!=-1) ans = min(ans,getv(sz[node],sz[big[splitnode]]));
return ans;
}
else{
int remsize = n-sz[node];
int thing = remsize/2;
if (thing==0){
return 999999999;
}
int imptnode = node;
for (int x = 19; x>=0; x--){
if (pa[imptnode][x]!=0 && hd[pa[imptnode][x]]!=1){
imptnode = pa[imptnode][x];
}
}
int bef = imptnode;
imptnode = pa[imptnode][0];
if (sz[big[imptnode]]>=thing){
//printf("far main branch\n");
int t2 = lower_bound(paths[1].begin(),paths[1].end(),make_pair(1-thing,-1))-paths[1].begin();
int splitnode = paths[1][t2-1].second;
int ans = getv(sz[node],sz[splitnode]);
if (big[splitnode]!=-1){
ans = min(ans,getv(sz[node],sz[big[splitnode]]));
}
return ans;
}
//printf("near main branch\n");
int tt = lower_bound(paths[1].begin(),paths[1].end(),make_pair(-thing-sz[node]+1,-1))-paths[1].begin();
int splitnode = paths[1][tt-1].second;
int ans = getv(sz[node],sz[splitnode]-sz[node]);
if (big[splitnode]!=-1) ans = min(ans,getv(sz[node],sz[big[splitnode]]));
if (bef!=node) ans = min(ans,getv(sz[node],sz[bef]-sz[node]));
return ans;
}
}
int main(){
scanf("%d",&n);
for (int x = 0; x<n-1; x++){
int a,b;
scanf("%d%d",&a,&b);
adjl[a].push_back(b);
adjl[b].push_back(a);
}
dfs(1,0);
//printf("dfs done\n");
decomp(1,0,1);
//printf("decomp done\n");
int ans = 999999999;
for (int x = 1; x<=n; x++){
ans = min(ans,check(x));
}
printf("%d",ans);
}
Compilation message
papricice.cpp: In function 'int main()':
papricice.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
papricice.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 6 |
Correct |
8 ms |
9964 KB |
Output is correct |
| 7 |
Correct |
9 ms |
10100 KB |
Output is correct |
| 8 |
Correct |
10 ms |
9964 KB |
Output is correct |
| 9 |
Correct |
8 ms |
9964 KB |
Output is correct |
| 10 |
Correct |
9 ms |
10092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 6 |
Correct |
8 ms |
9964 KB |
Output is correct |
| 7 |
Correct |
9 ms |
10100 KB |
Output is correct |
| 8 |
Correct |
10 ms |
9964 KB |
Output is correct |
| 9 |
Correct |
8 ms |
9964 KB |
Output is correct |
| 10 |
Correct |
9 ms |
10092 KB |
Output is correct |
| 11 |
Correct |
239 ms |
37612 KB |
Output is correct |
| 12 |
Correct |
277 ms |
39264 KB |
Output is correct |
| 13 |
Correct |
197 ms |
36716 KB |
Output is correct |
| 14 |
Correct |
208 ms |
37612 KB |
Output is correct |
| 15 |
Correct |
264 ms |
38764 KB |
Output is correct |
| 16 |
Correct |
162 ms |
35048 KB |
Output is correct |
| 17 |
Correct |
222 ms |
37868 KB |
Output is correct |
| 18 |
Correct |
266 ms |
44264 KB |
Output is correct |
| 19 |
Correct |
246 ms |
37676 KB |
Output is correct |
| 20 |
Correct |
252 ms |
39916 KB |
Output is correct |
