#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef long long ll;
#define int ll
typedef pair<int, int> pii;
typedef long double ld;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
const int N = 4e5 + 5;
int n;
list<int> g[N];
int tin[N], tout[N], timer, si[N];
struct tree {
tree *l{}, *r{};
pii v{+inf, -inf};
tree(int tl = 0, int tr = n) {
if(tl < tr) {
int tm = tl + tr >> 1;
l = new tree(tl, tm);
r = new tree(tm + 1, tr);
}
}
void add(int u, int tl = 0, int tr = n) {
umin(v.ft, tout[u]);
umax(v.sd, tin[u]);
if(tl == tr) return;
int tm = tl + tr >> 1;
si[u] <= tm
? l->add(u, tl, tm)
: r->add(u, tm + 1, tr);
}
pii get(int L, int R, int tl = 0, int tr = n) {
if(L > R) return {+inf, -inf};
if(L == tl && R == tr) return v;
int tm = tl + tr >> 1;
pii le = l->get(L, min(R, tm), tl, tm); ++tm;
pii ri = r->get(max(tm, L), R, tm, tr);
return {min(le.ft, ri.ft), max(le.sd, ri.sd)};
}
} *t;
void init(int v = 0, int pr = -1) {
tin[v] = timer++;
si[v] = 1;
g[v].remove(pr);
for(int u : g[v])
init(u, v),
si[v] += si[u];
tout[v] = timer++;
}
set<int> f, fg;
int dfs(int v = 0) {
int a = si[v];
int res = +inf;
if(!f.empty()) {
auto it = f.lower_bound(a + (n - a + 1 >> 1));
if(it != f.end()) {
int b = *it - a;
int c = n - a - b;
if(b > c) swap(b, c);
umin(res, max(abs(b - c), max(
abs(a - b),
abs(a - c))));
}
}
if(!fg.empty()) {
auto it2 = fg.lower_bound(n - a + 1 >> 1);
if(it2 != fg.end()) {
int b = *it2;
int c = n - a - b;
umin(res, max(abs(b - c), max(
abs(a - b),
abs(a - c))));
}
}
if(!g[v].empty()) {
f.insert(a);
fg.insert(n - a);
for(int u : g[v])
umin(res, dfs(u));
f.erase(a);
fg.erase(n - a);
}
return res;
}
bool works(int d) {
for(int i = 0; i < n; ++i) {
int a = si[i];
if(a * 3 > n) continue;
if(a * 3 + d * 2 < n) continue;
pii z = t->get(max(a, n - a - a - d),
min(n - a - a, a + d));
if(z.ft < tin[i] || z.sd > tout[i]) return true;
}
return false;
}
void solve() {
cin >> n;
for(int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
init();
t = new tree();
for(int i = 0; i < n; ++i)
t->add(i);
int l = 0, r = dfs();
while(l < r) {
int m = l + r >> 1;
works(m)
? r = m
: l = m + 1;
}
cout << l << endl;
#ifdef KEK
timer = 0;
for(int i = 0; i < n; ++i)
g[i].clear();
f.clear();
fg.clear();
#endif // KEK
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
Compilation message
papricice.cpp: In constructor 'tree::tree(ll, ll)':
papricice.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int tm = tl + tr >> 1;
| ~~~^~~~
papricice.cpp: In member function 'void tree::add(ll, ll, ll)':
papricice.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int tm = tl + tr >> 1;
| ~~~^~~~
papricice.cpp: In member function 'pii tree::get(ll, ll, ll, ll)':
papricice.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int tm = tl + tr >> 1;
| ~~~^~~~
papricice.cpp: In function 'll dfs(ll)':
papricice.cpp:80:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | auto it = f.lower_bound(a + (n - a + 1 >> 1));
| ~~~~~~^~~
papricice.cpp:91:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | auto it2 = fg.lower_bound(n - a + 1 >> 1);
| ~~~~~~^~~
papricice.cpp: In function 'void solve()':
papricice.cpp:138:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
138 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 6 |
Correct |
9 ms |
10092 KB |
Output is correct |
| 7 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 8 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 9 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 10 |
Correct |
8 ms |
10092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 6 |
Correct |
9 ms |
10092 KB |
Output is correct |
| 7 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 8 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 9 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 10 |
Correct |
8 ms |
10092 KB |
Output is correct |
| 11 |
Correct |
337 ms |
45932 KB |
Output is correct |
| 12 |
Incorrect |
372 ms |
45804 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
