#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int n,ans = 1e18 + 7,subt[N];
vector < int > tree[N];
multiset < int > path , notpath;
inline int eval(int a , int b , int c){
return max({abs(a-b) , abs(a-c) , abs(b-c)});
}
inline vector < int > closest_set(int tar , multiset < int > &ste){
vector < int > ret;
auto hi = ste.lower_bound(tar);
auto lo = --ste.lower_bound(tar);
if(hi != ste.end())ret.push_back(*hi);
if(hi != ste.begin())ret.push_back(*lo);
return ret;
}
inline void dfs0(int node , int past){
subt[node] = 1;
for(auto itr : tree[node]){
if(itr != past){
dfs0(itr,node);
subt[node] += subt[itr];
}
}
}
inline void dfs1(int node , int past){
if(path.size()){
for(auto cand : closest_set((n+subt[node])/2 , path)){
ans = min(ans , eval(n-cand,cand-subt[node],subt[node]));
}
}
if(notpath.size()){
for(auto cand : closest_set((n-subt[node])/2 , notpath)){
ans = min(ans , eval(n-cand-subt[node],cand,subt[node]));
}
}
for(auto itr : tree[node]){
if(itr != past){
path.insert(subt[itr]);
dfs1(itr,node);
path.erase(path.find(subt[itr]));
notpath.insert(subt[itr]);
}
}
}
void solve(){
cin >> n;
for(int i = 1;i<n;i++){
int u,v;cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
//precalc : subtree size
dfs0(1,0);
path.insert(subt[1]);
dfs1(1,0);
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
2 ms |
5220 KB |
Output is correct |
7 |
Correct |
2 ms |
5280 KB |
Output is correct |
8 |
Correct |
2 ms |
5212 KB |
Output is correct |
9 |
Correct |
3 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
5328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4956 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
2 ms |
5220 KB |
Output is correct |
7 |
Correct |
2 ms |
5280 KB |
Output is correct |
8 |
Correct |
2 ms |
5212 KB |
Output is correct |
9 |
Correct |
3 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
5328 KB |
Output is correct |
11 |
Correct |
174 ms |
23504 KB |
Output is correct |
12 |
Correct |
239 ms |
23288 KB |
Output is correct |
13 |
Correct |
164 ms |
24288 KB |
Output is correct |
14 |
Correct |
146 ms |
23756 KB |
Output is correct |
15 |
Correct |
220 ms |
23264 KB |
Output is correct |
16 |
Correct |
143 ms |
23844 KB |
Output is correct |
17 |
Correct |
176 ms |
23560 KB |
Output is correct |
18 |
Correct |
174 ms |
29268 KB |
Output is correct |
19 |
Correct |
219 ms |
23800 KB |
Output is correct |
20 |
Correct |
171 ms |
23556 KB |
Output is correct |