| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1317078 | vuviet | Papričice (COCI20_papricice) | C++20 | 0 ms | 0 KiB |
/**
* Author: tlamtruong - Trương Thùy Lâm
* Studies at: Le Hong Phong High School for the Gifted
**/
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e5 + 5;
vector<int> children[maxn];
int n, sz[maxn], ans = maxn;
set<int> P, Q;
void depth_search(int u, int p)
{
sz[u] = 1;
for (int v : children[u])
if (v != p)
depth_search(v, u), sz[u] += sz[v];
}
void Update(int u, set<int> &S, int val, int ok)
{
auto it = S.lower_bound(val);
if (it != S.end())
{
int mx = max({n - *it, *it - sz[u], sz[u]});
int mi = min({n - *it, *it - sz[u], sz[u]});
if (ok == 0)
{
mx = max({n - *it - sz[u], *it, sz[u]});
mi = mix({n - *it - sz[u], *it, sz[u]});
}
ans = min(ans, mx - mi);
}
if (it != S.begin())
{
--it;
int mx = max({n - *it, *it - sz[u], sz[u]});
int mi = min({n - *it, *it - sz[u], sz[u]});
if (ok == 0)
{
mx = max({n - *it - sz[u], *it, sz[u]});
mi = mix({n - *it - sz[u], *it, sz[u]});
}
ans = min(ans, mx - mi);
}
}
void DFSVisit(int u, int p)
{
P.insert(sz[u]);
Update(u, P, (n + sz[u]) / 2, 1);
Update(u, Q, (n - sz[u]) / 2, 0);
for (int v : children[u])
if (v != p)
DFSVisit(v, u);
P.erase(P.find(sz[u]));
Q.insert(sz[u]);
}
void ReadData()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 2; i <= n; ++i)
{
int x, y;
cin >> x >> y;
children[x].push_back(y);
children[y].push_back(x);
}
}
void Solve()
{
depth_search(1, 1);
DFSVisit(1, 1);
cout << ans;
}
int main()
{
ReadData();
Solve();
return 0;
}