# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 2e5 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
using namespace std;
int n, timer;
vector <int> g[maxn];
int sz[maxn];
int tin[maxn];
int tout[maxn];
int a[2003][2003];
void dfs (int v)
{
tin[v] = ++timer;
sz[v] = 1;
for (int to : g[v])
{
if (!sz[to])
{
dfs(to);
sz[v] += sz[to];
}
}
tout[v] = timer;
}
bool is_anc (int u, int v)
{
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
void ma1n (/* SABR */)
{
cin >> n;
for (int i = 1, u, v; i < n; ++i)
{
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
a[u][v] = 1;
a[v][u] = 1;
}
dfs(1);
int ans = n;
for (int u = 1; u <= n; ++u)
{
for (int v = 1; v <= n; ++v)
{
if (u != v && !a[u][v] && !a[v][u])
{
vector <int> x;
if (is_anc(u, v))
{
x.pb(sz[v]);
x.pb(sz[u] - sz[v] - 1);
x.pb(n - sz[u] + 1);
}
else if (is_anc(v, u))
{
x.pb(sz[u]);
x.pb(sz[v] - sz[u] - 1);
x.pb(n - sz[v] + 1);
}
else
{
x.pb(sz[u]);
x.pb(sz[v]);
x.pb(n - sz[u] - sz[v]);
}
sort(x.begin(), x.end());
ans = min(ans, x.back() - x[0]);
}
}
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << ' ';
ma1n();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
