#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> adj[200200];
multiset<int> st[200200];
int sz[200200], num[200200], n, ans = 1e9, cnt;
void dfs0(int s, int pa = -1){
sz[s] = 1;
for (auto &v:adj[s]) if (pa!=v){
dfs0(v, s);
sz[s] += sz[v];
}
}
void calc2(int x, int y){
//printf("%d %d\n", x, y);
ans = min(ans, max({x, y, n-x-y})-min({x, y, n-x-y}));
}
void calc(int x, multiset<int> &S, int t){
if (S.empty()) return;
calc2(x, *S.begin()-t);
calc2(x, *S.rbegin()-t);
multiset<int>::iterator iter[] = {S.lower_bound(x), S.lower_bound(n-x*2), S.lower_bound((n-x+1)/2)};
for (int i=0;i<3;i++) if (iter[i]!=S.end()) calc2(x, *iter[i]-t);
multiset<int>::iterator iter2[] = {S.upper_bound(x), S.upper_bound(n-x*2), S.upper_bound((n-x+1)/2)};
for (int i=0;i<3;i++) if (iter2[i]!=S.begin()) calc2(x, *(--iter2[i])-t);
}
void _move(int x, int y){
for (auto &z:st[x]) st[y].insert(z);
}
multiset<int> cur;
void dfs(int s, int pa = -1){
if (pa!=-1){
calc(sz[s], cur, sz[s]);
cur.insert(sz[s]);
}
if (adj[s].size()==1 && pa!=-1){
st[cnt].insert(1);
num[s] = cnt;
cnt++;
cur.erase(cur.find(1));
return;
}
for (auto &v:adj[s]) if (v!=pa){
if (sz[v]>sz[adj[s][0]] || adj[s][0]==pa) swap(v, adj[s][0]);
}
for (auto &v:adj[s]) if (v!=pa) dfs(v, s);
for (int i=1;i<(int)adj[s].size();i++) if (adj[s][i]!=pa){
for (auto &x:st[num[adj[s][i]]]) calc(x, st[num[adj[s][0]]], 0);
_move(num[adj[s][i]], num[adj[s][0]]);
}
st[num[adj[s][0]]].insert(sz[s]);
num[s] = num[adj[s][0]];
if (pa!=-1) cur.erase(cur.find(sz[s]));
}
int main(){
scanf("%d", &n);
for (int i=0;i<n-1;i++){
int x, y;
scanf("%d %d", &x, &y);
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs0(1);
dfs(1);
printf("%d\n", ans);
return 0;
}
Compilation message
papricice.cpp: In function 'int main()':
papricice.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
papricice.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
