#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define int long long
const int INF = 1e18;
void solve(){
int n; cin >> n;
vector<vector<int>> adj(n+1);
for(int i=0; i<n-1; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> sub(n+1);
map<int, int> a, b;
function<void(int, int)> dfs0 = [&](int s, int e){
sub[s] = 1;
for(auto &u:adj[s]){
if(u == e) continue;
dfs0(u, s);
sub[s] += sub[u];
}
};
dfs0(1, 0);
int ans = INF;
function<void(int, int)> dfs = [&](int s, int e){
auto it1 = a.lower_bound((n+sub[s])/2);
auto it2 = b.lower_bound((n-sub[s])/2);
if(!a.empty()){
if(it1 != a.end()) ans = min(ans, max({sub[s], it1->F-sub[s], n-it1->F}) - min({sub[s], it1->F-sub[s], n-it1->F}));
if(it1 != a.begin()) it1--, ans = min(ans, max({sub[s], it1->F-sub[s], n-it1->F}) - min({sub[s], it1->F-sub[s], n-it1->F}));
}
if(!b.empty()){
if(it2 != b.end()) ans = min(ans, max({sub[s], it2->F, n-it2->F-sub[s]}) - min({sub[s], it2->F, n-it2->F-sub[s]}));
if(!b.empty() && it2 != b.begin()) it2--, ans = min(ans, max({sub[s], it2->F, n-it2->F-sub[s]}) - min({sub[s], it2->F, n-it2->F-sub[s]}));
}
a[sub[s]]++;
for(auto &u:adj[s]){
if(u == e) continue;
dfs(u, s);
}
a[sub[s]]--;
if(a[sub[s]] == 0) a.erase(sub[s]);
b[sub[s]]++;
};
dfs(1, 0);
cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
218 ms |
16504 KB |
Output is correct |
12 |
Correct |
226 ms |
16568 KB |
Output is correct |
13 |
Correct |
159 ms |
17096 KB |
Output is correct |
14 |
Correct |
166 ms |
16732 KB |
Output is correct |
15 |
Correct |
194 ms |
16460 KB |
Output is correct |
16 |
Correct |
108 ms |
16176 KB |
Output is correct |
17 |
Correct |
163 ms |
16612 KB |
Output is correct |
18 |
Correct |
193 ms |
27696 KB |
Output is correct |
19 |
Correct |
158 ms |
16756 KB |
Output is correct |
20 |
Correct |
171 ms |
16564 KB |
Output is correct |