#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
vector <vector<int> > adj(N);
int under[N], n, mn = inf;
int val[3];
void label(int node, int ata) {
under[node] = 1;
for(auto it:adj[node]) {
if(it == ata) continue;
label(it, node);
under[node] += under[it];
// cout << node << " " << it << " " << under[it] << "\n";
}
}
void label(int node) {
memset(under, 0, N * sizeof(int));
label(node, 0);
}
int center(int node, int ata) {
int to = 0;
for(auto it:adj[node]) {
if(it == ata) continue;
if(under[it] >= (n + 1) / 2) {
to = it;
break;
}
}
if(!to) return node;
return center(to, node);
}
int push(int node, int ata) {
int mx = 0, mxnode = 0;
for(auto it:adj[node]) {
if(it == ata) continue;
if(under[it] > mx) {
mx = under[it];
mxnode = it;
}
}
return mxnode;
}
int32_t main(){
fast
cin>>n;
for(int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
label(1);
// for(int i = 1; i <= n; i++) {
// cout << under[i] << " ";
// } cout << "\n";
int st = center(1, 0);
// cout << st << "\n";
label(st);
// for(int i = 1; i <= n; i++) {
// cout << under[i] << " ";
// } cout << "\n";
int a = st, b = 0;
for(auto &it:adj[a]) {
if(under[it] > under[b]) {
b = it;
}
}
val[0] = under[st] - under[b]; // a için
val[1] = 0;
val[2] = under[b]; // b için
// cout << a << " " << b << "\n";
int ata = b, atb = a;
while(val[0] > val[1] or val[2] > val[1]) {
// cout << val[0] << " " << val[1] << " " << val[2] << "\n";
// cout << a << " " << b << "\n";
if(val[0] > val[2]) {
int prev = val[0];
a = push(a, ata);
val[1] += prev - under[a];
val[0] = under[a];
ata = a;
}
else {
int prev = val[2];
b = push(b, atb);
val[1] += prev - under[b];
val[2] = under[b];
atb = b;
}
mn = min(mn, max(max(abs(val[0] - val[1]), abs(val[0] - val[2])), abs(val[1] - val[2])));
}
// cout << val[0] << " " << val[1] << " " << val[2] << "\n";
// cout << a << " " << b << "\n";
mn = min(mn, max(max(abs(val[0] - val[1]), abs(val[0] - val[2])), abs(val[1] - val[2])));
cout << mn << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Execution timed out |
1083 ms |
6492 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Execution timed out |
1083 ms |
6492 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Execution timed out |
1083 ms |
6492 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |