#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
typedef long long ll;
const ll oo = 1e9;
const ll N = 1e6;
vector <vector <ll> > a;
ll sz[N];
ll sub_sz[N];
ll kol;
ll n;
bool mrk[N];
ll ans = oo;
ll calcsz(ll x, ll y)
{
sz[x] = 1;
for (ll i = 0; i < a[x].size(); i++)
if (a[x][i] != y) sz[x] += calcsz(a[x][i], x);
return sz[x];
}
ll calc(ll x, ll y)
{
sub_sz[x] = 1;
if (mrk[x]) return sub_sz[x];
for (ll i = 0; i < a[x].size(); i++)
if (a[x][i] != y) sub_sz[x] += calc(a[x][i], x);
return sub_sz[x];
}
ll find_centroid(ll x, ll y)
{
for (ll i = 0; i < a[x].size(); i++)
if (a[x][i] != y && !mrk[a[x][i]] && sub_sz[a[x][i]] >= kol / 2) return find_centroid(a[x][i], x);
return x;
}
void Rec(ll x, ll y, vector <ll> *k)
{
if (sz[x] > sz[y]) k -> pb(n - sz[y]);
else k -> pb(sz[x]);
if (mrk[x]) return;
for (ll i = 0; i < a[x].size(); i++)
if (a[x][i] != y) Rec(a[x][i], x, k);
}
void Centr_Tree(ll x)
{
if (mrk[x]) return;
kol = calc(x, x);
x = find_centroid(x, x);
mrk[x] = 1;
vector <ll> pr[a[x].size()];
for (ll i = 0; i < a[x].size(); i++) pr[i].clear();
for (ll i = 0; i < a[x].size(); i++) Rec(a[x][i], x, &pr[i]);
for (int i = 0; i < a[x].size(); i++) sort(pr[i].begin(), pr[i].end());
ll nom = 0;
for (ll i = 1; i < a[x].size(); i++)
{
ll nom1 = i;
if (pr[nom1].size() > pr[nom].size()) swap(nom, nom1);
for (int j1 = 0; j1 < pr[nom1].size(); j1++)
{
for (int j = 0; j < pr[nom].size(); j++) ans = min(ans, max(n - pr[nom1][j1] - pr[nom][j], max(pr[nom1][j1], pr[nom][j])) - min(n - pr[nom1][j1] - pr[nom][j], min(pr[nom1][j1], pr[nom][j])));
int ps;
auto j = lower_bound(pr[nom].begin(), pr[nom].end(), pr[nom1][j1]);
if (j != pr[nom].end())
{
ps = j - pr[nom].begin();
ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
}
j = upper_bound(pr[nom].begin(), pr[nom].end(), pr[nom1][j1]);
if (j != pr[nom].end())
{
ps = j - pr[nom].begin();
ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
}
int l = 0, r = pr[nom].size() - 1;
while (l < r)
{
int mdl = (l + r + 1) >> 1;
if (n - pr[nom1][j1] - pr[nom][mdl] < pr[nom1][j1]) r = mdl - 1;
else l = mdl;
}
{
ps = l;
ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
}
l++;
if (l < pr[nom].size())
{
ps = l;
ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
}
l = 0, r = pr[nom].size() - 1;
while (l < r)
{
int mdl = (l + r + 1) >> 1;
if (n - pr[nom1][j1] - pr[nom][mdl] < pr[nom1][j1]) r = mdl - 1;
else l = mdl;
}
{
ps = l;
ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
}
l++;
if (l < pr[nom].size())
{
ps = l;
ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
}
}
for (ll j = 0; j < pr[nom1].size(); j++) pr[nom].pb(pr[nom1][j]);
}
for (ll i = 0; i < a[x].size(); i++) Centr_Tree(a[x][i]);
}
int main() {
ios_base::sync_with_stdio(0);
iostream::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
a.resize(n);
for (ll i = 0; i < n - 1; i++)
{
ll x, y;
cin >> x >> y;
a[--x].pb(--y);
a[y].pb(x);
}
calcsz(0, 0);
Centr_Tree(0);
cout << ans;
}
Compilation message
papricice.cpp: In function 'll calcsz(ll, ll)':
papricice.cpp:24:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (ll i = 0; i < a[x].size(); i++)
| ~~^~~~~~~~~~~~~
papricice.cpp: In function 'll calc(ll, ll)':
papricice.cpp:33:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (ll i = 0; i < a[x].size(); i++)
| ~~^~~~~~~~~~~~~
papricice.cpp: In function 'll find_centroid(ll, ll)':
papricice.cpp:40:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (ll i = 0; i < a[x].size(); i++)
| ~~^~~~~~~~~~~~~
papricice.cpp: In function 'void Rec(ll, ll, std::vector<long long int>*)':
papricice.cpp:50:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (ll i = 0; i < a[x].size(); i++)
| ~~^~~~~~~~~~~~~
papricice.cpp: In function 'void Centr_Tree(ll)':
papricice.cpp:63:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (ll i = 0; i < a[x].size(); i++) pr[i].clear();
| ~~^~~~~~~~~~~~~
papricice.cpp:64:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (ll i = 0; i < a[x].size(); i++) Rec(a[x][i], x, &pr[i]);
| ~~^~~~~~~~~~~~~
papricice.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < a[x].size(); i++) sort(pr[i].begin(), pr[i].end());
| ~~^~~~~~~~~~~~~
papricice.cpp:67:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (ll i = 1; i < a[x].size(); i++)
| ~~^~~~~~~~~~~~~
papricice.cpp:71:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int j1 = 0; j1 < pr[nom1].size(); j1++)
| ~~~^~~~~~~~~~~~~~~~~
papricice.cpp:73:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int j = 0; j < pr[nom].size(); j++) ans = min(ans, max(n - pr[nom1][j1] - pr[nom][j], max(pr[nom1][j1], pr[nom][j])) - min(n - pr[nom1][j1] - pr[nom][j], min(pr[nom1][j1], pr[nom][j])));
| ~~^~~~~~~~~~~~~~~~
papricice.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if (l < pr[nom].size())
| ~~^~~~~~~~~~~~~~~~
papricice.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | if (l < pr[nom].size())
| ~~^~~~~~~~~~~~~~~~
papricice.cpp:122:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (ll j = 0; j < pr[nom1].size(); j++) pr[nom].pb(pr[nom1][j]);
| ~~^~~~~~~~~~~~~~~~~
papricice.cpp:124:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (ll i = 0; i < a[x].size(); i++) Centr_Tree(a[x][i]);
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
8 ms |
620 KB |
Output is correct |
| 7 |
Correct |
8 ms |
620 KB |
Output is correct |
| 8 |
Correct |
8 ms |
620 KB |
Output is correct |
| 9 |
Correct |
8 ms |
620 KB |
Output is correct |
| 10 |
Correct |
9 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
8 ms |
620 KB |
Output is correct |
| 7 |
Correct |
8 ms |
620 KB |
Output is correct |
| 8 |
Correct |
8 ms |
620 KB |
Output is correct |
| 9 |
Correct |
8 ms |
620 KB |
Output is correct |
| 10 |
Correct |
9 ms |
620 KB |
Output is correct |
| 11 |
Execution timed out |
1085 ms |
18152 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
