PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Yuriy Fedorov
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic Programming, Treap
PROBLEM
You are given a tree with N vertices rooted at vertex 1. There are M blue tokens and 1 red token. For each valid i, the i^{th} blue token appears at the root at an integer time t_i seconds and moves to a leaf vertex v_i, crossing one edge per second. In the next second after reaching v_i, this token disappears. You control the red token.
Additionally, you have a hidden ability called K-teleport, which can be used any number of times. Whenever K-teleport is used to move the red token from its current vertex u to some vertex v of your choice (possibly u itself), it phases out of existence (so it cannot clash with any blue token) and appears in v at an integer moment in time of your choice which is at least K⋅dist(u,v) seconds later. Here, dist(u,v)dist(u,v) denotes the shortest distance between vertices u and v.
At each integer moment in time, the red token is not allowed to be in the same vertex as any blue token. Find the minimum time at which the red token can reach the root without clashing with any blue token.
EXPLANATION:
Whole the explanation was given by the author himself, to give credit where it’s due.
It is quite clear that it doesn’t make any sense for us to go down since we need to reach the root as soon as possible. We can use Dynamic Programmin for this. Let’s move towards it:
DP[V][0] is defined as the minimum time to be in the normal state at the vertex V and DP[V][1] is defined as the minimum time to be in the teleported state at the vertex V.
How to relax to an ancestor?
Let’s define a minimum time t_1 such that, during time (t_1-1) there is no blue chip present on vertex V and at time t_1 there is no blue chip present on its parent. Let us represent vertex of V as V_p Then,
Also, we define a minimum time t_2 which is greater than or equal to the teleported state of the vertex V_p, such that at time t_2 there is no blue chip present on vertex V_p. Then
If we use K-teleport for moving from vertex V to its parent vertex. Then in this case of the teleported state, the transition will be:
We need to carefully set the initial state of the DP of the leaf, so as not to be immediately together with the blue chip.
Handling Queries
Let’s store in each vertex V a treap with ordinal statistics (answer the query number of numbers < K) of all times (counting from the root for ease of implementation) when there is food in this vertex. And we will store another treap (second treap), where there will be all the times with food, and the same times + 2 (because if we get a time ban in the ancestor).
Now we use the technique of transfusion from less to more.
-
Let’s take a list of bad times for all children. And then we will look for a transition of DP from a larger child. Let’s sort all the times. If the amount of food in the second treap on the interval is equal to the size of the interval, then it means that there will not be a suitable time point, otherwise, we will do a binary search by time in this interval.
-
Now we will pour everything into a larger child. Then we will do the same with small children, only for their size, and it makes behind his size us to refer to the first treap.
-
Other queries are also clear as they are made by binary search with ordinal statistics.
TIME COMPLEXITY:
O(N * log^2 (M) per test case
SOLUTIONS:
Setter
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <algorithm>
#include <set>
#define all(a) a.begin(), a.end()
using namespace std;
mt19937 rnd(777);
struct node {
int L = -1, R = -1, size = 1, y = rnd(), who;
node (int c) {who = c;}
node() {}
};
const int Q = 1e7;
int timer = 0;
node t[Q];
int size(int a) {
if (a == -1)
return 0;
return t[a].size;
}
void update(int a) {
t[a].size = size(t[a].L) + size(t[a].R) + 1;
}
bool find(int a, int x) {
if (a == -1)
return false;
else if (t[a].who == x)
return true;
else if (t[a].who < x)
return find(t[a].R, x);
else
return find(t[a].L, x);
}
int add_node(int x) {
// t.emplace_back(x);
t[timer++] = node(x);
return timer - 1;
}
pair<int, int> split_val(int a, int k) {
if (a == -1)
return make_pair(-1, -1);
if (t[a].who < k) {
auto z = split_val(t[a].R, k);
t[a].R = z.first;
update(a);
return make_pair(a, z.second);
} else {
auto z = split_val(t[a].L, k);
t[a].L = z.second;
update(a);
return make_pair(z.first, a);
}
}
int _insert(int a, int new_node) {
if (a == -1)
return new_node;
if (t[a].y <= t[new_node].y) {
auto z = split_val(a, t[new_node].who);
t[new_node].L = z.first, t[new_node].R = z.second;
update(new_node);
return new_node;
} else {
if (t[a].who < t[new_node].who)
t[a].R = _insert(t[a].R, new_node);
else
t[a].L = _insert(t[a].L, new_node);
update(a);
return a;
}
}
int insert(int a, int x) {
if (find(a, x))
return a;
return _insert(a, add_node(x));
}
void list_node(int a, vector<int> &ans) {
if (a == -1)
return;
list_node(t[a].L, ans);
ans.push_back(t[a].who);
list_node(t[a].R, ans);
}
int count_less(int a, int k) {
if (a == -1)
return 0;
if (t[a].who > k)
return count_less(t[a].L, k);
else
return count_less(t[a].R, k) + 1 + size(t[a].L);
}
int count_greater(int a, int k) {
if (a == -1)
return 0;
if (t[a].who < k)
return count_greater(t[a].R, k);
else
return count_greater(t[a].L, k) + 1 + size(t[a].R);
}
void print(int a) {
if (a == -1)
return;
print(t[a].L);
cout << t[a].who << ' ';
print(t[a].R);
}
const int N = 2e5 + 228;
const int INF = 3 * N;
vector<int> G[N];
vector<int> ev[N];
pair<int, int> dp[N];
pair<int, int> a[N];
void dfs_solve(int v, int p, int h, int x) {
bool was = false;
for (int i : G[v]) {
if (i == p)
continue;
was = true;
dfs_solve(i, v, h + 1, x);
dp[v].second = min(dp[v].second, dp[i].second + x);
}
if (!was) {
for (int j : ev[v]) {
a[v].first = insert(a[v].first, j);
a[v].second = insert(a[v].second, j);
a[v].second = insert(a[v].second, j + 2);
}
int l = -h, r = INF;
while (r - l > 1) {
int m = (l + r) / 2;
if (size(a[v].first) - count_less(a[v].first, -1 - h) - count_greater(a[v].first, m) != m + h)
r = m;
else
l = m;
}
dp[v] = make_pair(l + h, l + h);
return;
}
for (int &i : G[v]) {
if (i == p) {
swap(i, G[v].back());
G[v].pop_back();
break;
}
}
int mx = 0;
for (int i = 0; i < (int) G[v].size(); ++i)
mx = (size(a[G[v][i]].first) > size(a[G[v][mx]].first) ? i : mx);
swap(G[v][0], G[v][mx]);
vector<int> all_food;
for (int i = 1; i < (int) G[v].size(); ++i)
list_node(a[G[v][i]].first, all_food);
all_food.push_back(INF);
all_food.push_back(-INF);
sort(all(all_food));
all_food.resize(unique(all(all_food)) - all_food.begin());
int new_v = G[v][0];
for (int i = 0; i < (int) all_food.size() - 1; ++i) {
if (all_food[i + 1] <= dp[new_v].first - h)
continue;
int L = max(dp[new_v].first - h, all_food[i]), R = all_food[i + 1];
if (size(a[new_v].second) - count_less(a[new_v].second, L) - count_greater(a[new_v].second, R) != R - L - 1) {
int l = L, r = R;
while (r - l > 1) {
int m = (l + r) / 2;
if (size(a[new_v].second) - count_less(a[new_v].second, L) - count_greater(a[new_v].second, m) != m - L - 1)
r = m;
else
l = m;
}
if (l == L)
exit(1);
dp[v].first = min(dp[v].first, l + h);
break;
}
}
a[v] = a[new_v];
for (int i : all_food) {
a[v].first = insert(a[v].first, i);
a[v].second = insert(a[v].second, i);
a[v].second = insert(a[v].second, i + 2);
}
for (int i = 1; i < (int) G[v].size(); ++i) {
int new_v = G[v][i];
vector<int> b = {-INF};
list_node(a[new_v].first, b);
b.push_back(INF);
for (int j = 0; j < (int) b.size() - 1; ++j) {
if (b[j + 1] + 2 <= dp[new_v].first - h)
continue;
int L = max(b[j] + 2, dp[new_v].first - h), R = b[j + 1] + 2;
if (size(a[v].first) - count_less(a[v].first, L) - count_greater(a[v].first, R) != R - L - 1) {
int l = L, r = R;
while (r - l > 1) {
int m = (l + r) / 2;
if (size(a[v].first) - count_less(a[v].first, L) - count_greater(a[v].first, m) != m - L - 1)
r = m;
else
l = m;
}
if (l == L)
exit(1);
dp[v].first = min(dp[v].first, l + h);
break;
}
}
}
int l = dp[v].second - h, r = dp[v].first + 2 - h;
while (r - l > 1) {
int m = (l + r) / 2;
if (size(a[v].first) - count_less(a[v].first, dp[v].second - 1 - h) - count_greater(a[v].first, m) != m - dp[v].second + h)
r = m;
else
l = m;
}
dp[v].first = min(dp[v].first, l + h);
dp[v].second = min(dp[v].second, dp[v].first);
}
void solve() {
int n, m, x, s;
cin >> n >> m >> x >> s;
timer = 0;
fill(dp, dp + n, make_pair(INF, INF));
fill(a, a + n, make_pair(-1, -1));
for (int i = 0; i < n; ++i) {
ev[i].clear();
G[i].clear();
}
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
G[a - 1].push_back(b - 1);
G[b - 1].push_back(a - 1);
}
while (m--) {
int t, v;
cin >> t >> v;
t -= s;
if (t >= 3 * N || t <= -3 * N)
continue;
ev[v - 1].push_back(t);
}
dfs_solve(0, 0, 0, x);
cout << dp[0].first + s << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
}