#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int inf = 1e9;
struct SegmentTree{
vector<int> tree;
void init(int n) {
int sz = 1 << __lg(n-1) + 2;
tree.assign(sz, inf);
}
void update(int node, int s, int e, int l, int r, int val) {
if (l > e || s > r) return;
if (l <= s && e <= r) {
tree[node] = min(tree[node], val);
return;
}
int mid = s + e >> 1;
update(node*2, s, mid, l, r, val);
update(node*2+1, mid+1, e, l, r, val);
}
int query(int node, int s, int e, int tar) {
if (s == e) return tree[node];
int mid = s + e >> 1;
if (tar <= mid) return min(tree[node], query(node*2, s, mid, tar));
return min(tree[node], query(node*2+1, mid+1, e, tar));
}
};
struct MN2{
pair<int,int> val1, val2;
};
struct Node{
int l, r;
MN2 val;
};
MN2 Merge(MN2 u, MN2 v) {
MN2 ret;
if (u.val1 > v.val1) swap(u, v);
ret.val1 = u.val1;
ret.val2 = u.val2;
if (v.val1.second != ret.val1.second && ret.val2 > v.val1)
ret.val2 = v.val1;
if (v.val2.second != ret.val1.second && ret.val2 > v.val2)
ret.val2 = v.val2;
return ret;
}
struct DynamicSegmentTree{
vector<Node> tree;
void init() {
tree.clear();
tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
}
void update(int node, int s, int e, int tar, pair<int,int> val) {
tree[node].val = Merge(tree[node].val, {val, {inf,-1}});
if (s == e) {
return;
}
int mid = s + e >> 1;
if (tar <= mid) {
if (tree[node].l == -1) {
tree[node].l = tree.size();
tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
}
update(tree[node].l, s, mid, tar, val);
}
else {
if (tree[node].r == -1) {
tree[node].r = tree.size();
tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
}
update(tree[node].r, mid+1, e, tar, val);
}
}
MN2 query(int node, int s, int e, int l, int r, bool f = false) {
if (l > e || s > r || node == -1) return {{inf,-1}, {inf,-1}};
if (l <= s && e <= r) return tree[node].val;
int mid = s + e >> 1;
return Merge(query(tree[node].l, s, mid, l, r, f), query(tree[node].r, mid+1, e, l, r, f));
}
};
SegmentTree seg;
int N, R, A, B;
vector<int> adj[300010];
vector<int> g[300010];
int down[300010], par[300010];
int dep[300010];
int in[300010], out[300010];
int pv;
int sz[300010];
int top[300010];
int chk[300010];
int getSize(int x, int p) {
sz[x] = 1;
for (auto &y : adj[x]) {
if (chk[y] || y == p) continue;
sz[x] += getSize(y, x);
}
return sz[x];
}
int getCent(int x, int p, int cap) {
for (auto &y : adj[x]) {
if (chk[y] || y == p) continue;
if (sz[y] * 2 > cap)
return getCent(y, x, cap);
}
return x;
}
set<int> ps[300010];
int cent[300010][20], dist[300010][20];
int sub[300010][20];
void dfs3(int x, int p, int lv, int S) {
sub[x][lv] = S;
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
cent[y][lv] = cent[x][lv];
dist[y][lv] = dist[x][lv] + 1;
dfs3(y, x, lv, S);
}
}
void dnc(int x, int lv) {
x = getCent(x, -1, getSize(x, -1));
int t = x;
while (t && !chk[t]) {
ps[x].insert(t);
t = par[t];
}
sub[x][lv] = x;
cent[x][lv] = x;
dist[x][lv] = 0;
for (auto &y : adj[x]) {
if (chk[y]) continue;
cent[y][lv] = x;
dist[y][lv] = 1;
dfs3(y, x, lv, y);
}
chk[x] = 1;
for (auto &y : adj[x]) {
if (chk[y]) continue;
dnc(y, lv+1);
}
}
void dfs(int x, int p) {
sz[x] = 1;
down[x] = 0;
for (auto &y : adj[x]) {
if (y == p) continue;
par[y] = x;
dep[y] = dep[x] + 1;
g[x].push_back(y);
dfs(y, x);
down[x] = max(down[x], down[y] + 1);
if (sz[g[x][0]] < sz[y]) swap(g[x][0], g[x].back());
sz[x] += sz[y];
}
}
void dfs2(int x) {
in[x] = ++ pv;
for (auto &y : g[x]) {
top[y] = y == g[x][0] ? top[x] : y;
dfs2(y);
}
out[x] = pv;
}
void HLDupdate(int x) {
int ori = x;
int cnt = B;
while (x) {
int tp = top[x];
if (dep[x] - dep[tp] + 1 < cnt) {
seg.update(1, 1, N, in[tp], in[x], ori);
cnt -= dep[x] - dep[tp] + 1;
}
else {
seg.update(1, 1, N, in[x]-cnt+1, in[x], ori);
break;
}
x = par[tp];
}
}
int dp[300010];
int dp2[300010];
vector<int> vtx[300010];
vector<pair<int,int>> poss[300010], imp[300010];
DynamicSegmentTree seg1[300010], seg2[300010];
void CentUpdate(int x) {
for (int lv=19; lv>=0; lv--) {
if (!cent[x][lv]) continue;
if (cent[x][lv] == x) continue;
int c = cent[x][lv];
int val;
if (poss[x].empty()) val = imp[x][0].first;
else val = poss[x][0].first;
if (sub[x][lv] == par[c]) {
if (ps[c].find(x) != ps[c].end()) {
if (poss[x].empty()) {
if (ps[c].find(imp[x][0].second) != ps[c].end())
val = imp[x][1].first;
}
else if (poss[x].size() == 1) {
if (ps[c].find(poss[x][0].second) != ps[c].end())
val = imp[x][0].first;
}
else {
if (ps[c].find(poss[x][0].second) != ps[c].end())
val = poss[x][1].first;
}
}
seg1[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
}
else {
seg1[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
seg2[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
}
}
}
int Centquery(int x) {
int ret = N + 1;
for (int lv=19; lv>=0; lv--) {
if (!cent[x][lv]) continue;
int d = B - dist[x][lv];
if (d < 0) continue;
int c = cent[x][lv];
int val;
if (poss[c].empty()) val = imp[c][0].first;
else val = poss[c][0].first;
if (x == c) {
ret = min(ret, val);
}
else {
if (poss[c].empty()) {
if (sub[x][lv] == imp[c][0].second)
val = imp[c][1].first;
}
else if (poss[c].size() == 1) {
if (sub[x][lv] == poss[c][0].second)
val = imp[c][0].first;
}
else {
if (sub[x][lv] == poss[c][0].second)
val = poss[c][1].first;
}
ret = min(ret, val);
}
if (d == 0) continue;
MN2 t = seg2[c].query(0, 1, N, 1, d);
//assert(t.val1.second != t.val2.second);
if (t.val1.second == sub[x][lv]) ret = min(ret, t.val2.first);
else ret = min(ret, t.val1.first);
}
assert(ret != N+1);
return ret;
}
//DynamicSegmentTree final[300010];
int simulate(int x, int p, int dist) {
if (dist > B) return N + 1;
int ret;
int d = 0;
for (auto &y : adj[x]) {
if (y == p || y == par[x]) continue;
d = max(d, down[y] + 1);
}
if (d < A) {
ret = x;
for (auto &y : adj[x]) {
if (y == p || y == par[x]) continue;
ret = min(ret, dp[y]);
}
}
else {
ret = 0;
for (auto &y : adj[x]) {
if (y == p || y == par[x]) continue;
if (down[y] >= A-1)
ret = max(ret, dp[y]);
}
}
for (auto &y : adj[x]) {
if (y == p) continue;
ret = min(ret, simulate(y, x, dist + 1));
}
return ret;
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
cin >> N >> R >> A >> B;
if (A <= B) {
cout << "1\n";
return 0;
}
for (int i=0; i<N-1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(R, 0);
top[R] = R;
dfs2(R);
seg.init(N);
int mxdep = 0;
for (int i=1; i<=N; i++) {
mxdep = max(mxdep, dep[i]);
vtx[dep[i]].push_back(i);
HLDupdate(i);
imp[i].push_back({i, -1});
seg1[i].init();
seg2[i].init();
}
dnc(1, 0);
for (int i=mxdep; i>=1; i--) {
for (auto &x : vtx[i]) {
sort(imp[x].begin(), imp[x].end());
sort(poss[x].begin(), poss[x].end());
reverse(poss[x].begin(), poss[x].end());
CentUpdate(x);
}
if (i+A-1 <= mxdep) {
for (auto &x : vtx[i+A-1]) {
dp2[x] = Centquery(x);
}
}
for (auto &x : vtx[i]) {
if (down[x] < A-1) {
dp[x] = min(par[x], seg.query(1, 1, N, in[x]));
imp[par[x]].push_back({dp[x], x});
}
else {
for (auto &y : vtx[i+A-1]) {
if (in[x] <= in[y] && in[y] <= out[x])
dp[x] = max(dp[x], dp2[y]);
}
poss[par[x]].push_back({dp[x], x});
}
//cout << i << ' ' << dp[x] << ' ' << x << '\n';
}
}
if (down[R] < A) {
int ans = R;
for (auto &x : vtx[1]) {
ans = min(ans, dp[x]);
}
cout << ans;
}
else {
int ans = 0;
for (auto &x : vtx[1]) {
if (down[x] >= A-1)
ans = max(ans, dp[x]);
}
cout << ans;
}
}
Compilation message
Main.cpp: In member function 'void SegmentTree::init(int)':
Main.cpp:12:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
12 | int sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
Main.cpp:21:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
Main.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void DynamicSegmentTree::update(int, int, int, int, std::pair<int, int>)':
Main.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'MN2 DynamicSegmentTree::query(int, int, int, int, int, bool)':
Main.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
67932 KB |
Output is correct |
| 2 |
Correct |
10 ms |
68084 KB |
Output is correct |
| 3 |
Correct |
9 ms |
67932 KB |
Output is correct |
| 4 |
Correct |
9 ms |
67884 KB |
Output is correct |
| 5 |
Correct |
9 ms |
68044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3391 ms |
848344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
80476 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
80592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
80476 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
80592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1118 ms |
189524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
80476 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
80592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
67932 KB |
Output is correct |
| 2 |
Correct |
10 ms |
68084 KB |
Output is correct |
| 3 |
Correct |
9 ms |
67932 KB |
Output is correct |
| 4 |
Correct |
9 ms |
67884 KB |
Output is correct |
| 5 |
Correct |
9 ms |
68044 KB |
Output is correct |
| 6 |
Incorrect |
3391 ms |
848344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
