#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5;
int n;
vector<int> graph[NMAX + 5];
vector<multiset<int> > sets;
int w[NMAX + 5];
multiset<int> down[NMAX + 5];
void predfs(int nod,int tata){
w[nod] = 1;
for(auto it:graph[nod]){
if(it != tata){
predfs(it,nod);
w[nod] += w[it];
}
}
}
void dfs2(int nod,int tata,int t,multiset<int> &s){
if(t == 1){
s.insert(w[nod]);
}
else{
s.erase(s.find(w[nod]));
}
for(auto it:graph[nod]){
if(it == tata){
continue;
}
dfs2(it,nod,t,s);
}
}
int compute(int a,int b,int c){
return max(max(a,b),c) - min(min(a,b),c);
}
int ans = 1e9;
void dfs(int nod,int tata){
if(tata != 0){
int target_val = (n - w[nod]) / 2;
multiset<int> :: iterator it;
for(auto s:sets){
it = s.lower_bound(target_val);
if(it == s.end() || *it == n - w[nod]){
;
}
else{
ans = min(ans,compute(w[nod],*it,n - w[nod] - *it));
}
if(it == s.begin()){
continue;
}
it--;
if(*it == n - w[nod]){
;
}
else{
ans = min(ans,compute(w[nod],*it,n - w[nod] - *it));
}
}
}
int bigChild =-1;
for(auto it:graph[nod]){
if(it == tata){
continue;
}
if(bigChild == -1 || w[it] > w[bigChild]){
bigChild = it;
}
}
for(auto it:graph[nod]){
if(it == tata || it == bigChild){
continue;
}
dfs2(it,nod,1,sets[0]);
}
if(bigChild != -1){
sets[0].insert(n - w[bigChild]);
dfs(bigChild,nod);
sets.push_back(multiset<int>());
sets.back().swap(down[bigChild]);
sets[0].erase(sets[0].find(n - w[bigChild]));
}
for(auto it:graph[nod]){
if(it == tata || it == bigChild){
continue;
}
dfs2(it,nod,-1,sets[0]);
sets[0].insert(n - w[it]);
dfs(it,nod);
sets[0].erase(sets[0].find(n - w[it]);
dfs2(it,nod,1,sets[0]);
}
if(bigChild != -1){
down[nod].swap(sets.back());
sets.pop_back();
}
for(auto it:graph[nod]){
if(it == tata || it == bigChild){
continue;
}
dfs2(it,nod,-1,sets[0]);
dfs2(it,nod,1,down[nod]);
}
}
int main(){
scanf("%d",&n);
for(int i = 1;i < n;i++){
int x,y;
scanf("%d %d",&x,&y);
graph[x].push_back(y);
graph[y].push_back(x);
}
sets.push_back(multiset<int>());
predfs(1,0);
dfs(1,0);
printf("%d\n",ans);
return 0;
}
Compilation message
papricice.cpp: In function 'void dfs(int, int)':
papricice.cpp:107:46: error: expected ')' before ';' token
107 | sets[0].erase(sets[0].find(n - w[it]);
| ~ ^
| )
papricice.cpp: In function 'int main()':
papricice.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
papricice.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
131 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
