This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5;
int n;
vector<int> graph[NMAX + 5];
vector<map<int,int> > sets;
int w[NMAX + 5];
map<int,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];
}
}
}
inline void add(map<int,int> &s,int val){
s[val]++;
}
inline void rem(map<int,int> &s,int val){
s[val]--;
if(s[val] == 0){
s.erase(val);
}
}
void dfs2(int nod,int tata,int t,map<int,int> &s) {
if(t == 1) {
add(s,w[nod]);
}
else {
rem(s,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;
map<int,int> :: iterator it;
for(auto s:sets) {
it = s.lower_bound(target_val);
if(it == s.end() || it->first == n - w[nod]) {
;
}
else {
ans = min(ans,compute(w[nod],it->first,n - w[nod] - it->first));
}
if(it == s.begin()) {
continue;
}
it--;
if(it->first == n - w[nod]) {
;
}
else {
ans = min(ans,compute(w[nod],it->first,n - w[nod] - it->first));
}
}
}
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) {
add(sets[0],n - w[bigChild]);
dfs(bigChild,nod);
sets.push_back(map<int,int>());
sets.back().swap(down[bigChild]);
rem(sets[0],n - w[bigChild]);
}
for(auto it:graph[nod]) {
if(it == tata || it == bigChild) {
continue;
}
dfs2(it,nod,-1,sets[0]);
add(sets[0],n - w[it]);
dfs(it,nod);
rem(sets[0],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(map<int,int>());
predfs(1,0);
dfs(1,0);
printf("%d\n",ans);
return 0;
}
Compilation message (stderr)
papricice.cpp: In function 'int main()':
papricice.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
138 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
papricice.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
142 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |