#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e3 + 5;
vector<int> adj[N + 5];
vector<int> child[N+5];
int sz[N + 5];
void dfs(int v, int last){
sz[v] = 1;
child[v].push_back(v);
for(auto u : adj[v]){
if(u != last) dfs(u , v);
}
for(auto u : adj[v]){
if(u == last) continue;
sz[v] += sz[u];
for(auto it : child[u]){
child[v].push_back(it);
}
}
}
int main(){
int n;
cin >> n;
for(int i = 1; i<n; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 1);
int ans = n;
for(int i = 2; i<=n; i++){
// cout << sz[i] << endl;
bool c[n+5];
for(int j = 0; j<=n; j++){
c[j] = false;
}
for(auto u : child[i]) c[u] = true;
int A, B, C;
for(int j = 2; j<=n; j++){
if(c[j]) C = sz[j], B = sz[i] - sz[j], A = n - sz[i];
else C = sz[j], B = sz[i], A = n - sz[i] - sz[j];
ans = min(ans, max(abs(A - B), max(abs(A - C), abs(B - C))));
// cout << i << " " << j << " " << A << " " << B << " " << C << endl;
}
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
9 ms |
600 KB |
Output is correct |
7 |
Incorrect |
9 ms |
1116 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
9 ms |
600 KB |
Output is correct |
7 |
Incorrect |
9 ms |
1116 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |