/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e9;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int eu[maxn];
int tin[maxn];
int tout[maxn];
vector<int> G[maxn];
int sz[maxn];
int l1 = 0;
int n;
vector<int> c[maxn];
int ans = 1e9;
void calc(int a, int b, int c)
{
ans = min(ans, max({a, b, c}) - min({a, b, c}));
}
int calc1(int a, int b, int c)
{
return max({a, b, c}) - min({a, b, c});
}
void dfs(int u, int pa)
{
eu[++l1] = u;
tin[u] = l1;
sz[u] = 1;
for (auto v : G[u])
{
if (v == pa)
continue;
dfs(v, u);
sz[u] += sz[v];
}
tout[u] = l1;
}
multiset<int> st;
void dfs1(int u, int pa)
{
if (pa != -1)
{
st.erase(st.find(sz[pa]));
st.insert(n - sz[u]);
if ((n - sz[u]) / 2 <= sz[u])
{
auto v = st.lower_bound(sz[u]);
if (v != st.end())
{
calc(sz[u], (*v), n - sz[u] - (*v));
}
}
else
{
auto v = st.lower_bound((n - sz[u]) / 2);
if (v != st.end())
{
calc(sz[u], (*v), n - sz[u] - (*v));
}
auto k = st.lower_bound(sz[u]);
if (v != st.begin())
{
v--;
if (v != st.end())
{
if ((*v) >= sz[u] && v != k)
{
calc(sz[u], (*v), n - sz[u] - (*v));
}
}
}
v = st.upper_bound((n - sz[u]) / 2);
if (v != st.end())
{
calc(sz[u], (*v), n - sz[u] - (*v));
}
if (v != st.begin())
{
v--;
if ((*v) >= sz[u] && v != k)
{
calc(sz[u], (*v), n - sz[u] - (*v));
}
}
auto v1 = st.lower_bound(n - sz[u] * 2);
if (v1 != st.end())
{
calc((*v1), sz[u], n - (*v1) - sz[u]);
}
}
}
for (auto v : G[u])
{
if (v == pa)
continue;
dfs1(v, u);
}
if (pa != -1)
{
st.insert(sz[pa]);
st.erase(st.find(n - sz[u]));
}
}
void solve()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
G[u].pb(v);
G[v].pb(u);
}
dfs(1, -1);
for (int i = 1; i <= n; i++)
{
st.insert(sz[i]);
}
dfs1(1, -1);
cout << ans << "\n";
}
signed main()
{
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
