Mission Minimpossible

Author : tnaveen2308

Required Knowledge : Graphs, Posets, DP, Advanced Data Structures

Time Complexity : $O(n + klog_2^2{k})$

Editorialist : tnaveen2308

Approach:

First, how do we find the answer in any time complexity? Let us construct a partially ordered set where each element is a single spy in one of the assignments. For two elements $x = (v_1, d_1)$ and $y = (v_2, d_2)$ we put $x < y$ if $x$ and $y$ could possibly be two assignments that the same spy can handle one after the other, that is, there is enough time to get from one safe-house to another, so that $\rho(v_1, v_2) \leq d_2 - d_1$, where $\rho(v_1, v_2)$ is the distance between the safe-houses, and $d_1$ and $d_2$ are respective day numbers of the two assignments. We can now see that the answer is the smallest number of $chains$ needed to cover all the vertices (a chain is a set of pairwise comparable elements of a p.o.set). By Dilworth's theorem, this is equal to the size of the largest $antichain$ (a set of pairwise incomparable elements). Clearly, if a largest antichain contains a spy from an assignment, then it must include all spies from this assignment as well. We can now solve the problem in something like $O(2^k)$ time by trying all subsets of assignments.

To get a better complexity we need to use the tree structure. To start, how do we check if a set of assignments forms an antichain? Here's one criterion that works:

Proposition. A set $S$ of assignments is an antichain iff:

• For each subtree of the root $v$, a subset of $S$ lying in that subtree is an antichain.
• There exists a time moment $T$ such that it is impossible to reach $v$ at time $T$ from any assignment in $S$ (possibly travelling back in time).

Indeed, if both of these conditions hold, than for any two assignments $(v_1, d_1)$ and $(v_2, d_2)$ happening in different subtrees we have $\rho(v_1, v_2) = \rho(v, v_1) + \rho(v, v_2) > |d_1 - T| + |d_2 - T| \geq |d_1 - d_2|$, hence these assignments are incomparable. On the other hand, if $S$ is an antichain, for any assignment $(v_i, d_i) \in S$ there is an interval of time moments $(l_i, r_i)$ such that we cannot reach the root at any of times in $(l_i, r_i)$. If two assignments $i$ and $j$ are incomparable, then $(l_i, r_i) \cap (l_j, r_j) \neq \emptyset$. But since we have a set of intervals with pairwise non-empty intersections, they must all share a common point, hence our time moment $T$ exists.

Note that in some cases $T$ is necessarily a non-integer: if there are two safe-houses at distance 1 from the root, and there are assignments happening at days 1 and 2 respectively at these safe-houses, than any $T \in (1, 2)$ will suffice. However, $T$ can always be either an integer or a half-integer, hence we can multiply all times and distances by 2 and assume $T$ is integer.

The solution is going to be subtree dynamic programming $dp_{v,t}$ — the total weight of the largest antichain in the subtree of $v$ such that no assignment can reach $v$ at time $t$. Recalculation is a bit tricky, so let's go step by step. First, if we have values of $dp_{v,t}$, and no assignments take place at $v$, how do we change $dp_{v,t}$ as we travel up the edge to the top of $v$? If the length of this edge is $l$, then the new values $dp'_{v,t}$ satisfy $dp'_{v,t} = \max_{t'=t-l}^{t+l} dp_{v,t'}$. Let's call this procedure "advancing $l$ steps forward".

How do we account for assignments at $v$? For an assignment $(v, t)$ with $s$ spies we cannot simply add $s$ to $dp_{v,t}$ since we can obviously reach $v$ at time $t$ from this assignment. Instead, the correct procedure is:

• advance the values 1 step;
• apply $dp'_{v,t} = \max(dp'_{v,t}, dp_{v,t} + s)$ for all assignments;
• advance the new values $l - 1$ steps.

Finally, to combine the answers from the subtrees $u_1, \ldots, u_k$ of a safe-house $v$ (after the advancements were made in them), we simply add them element-wise for each $t$: $dp_{v,t} = \sum_{u_i} dp_{u_i,t}$.

Of course, we cannot store the DP values themselves since there are too much of them to store. Instead, we will need to use a data structure that will maintain a piecewise constant function. More specifically, let us maintain the positions where the function changes values: for each $t$ such that $dp_{v,t} \neq dp_{v,t+1}$ we store the pair $(t, dp_{v,t+1} - dp_{v,t})$. How all of the above manipulations look like in terms of this difference structure?

• Element-wise sum of two functions is simply the union of the difference sets. (We may want to combine the differences with the same $t$ value, but for most implementations this is not necessary)
• When we advance $l$ steps forward, the borders with positive differences will more $l$ units to the left, and negative differences will move to the right. When two borders collide, then some of them get eliminated. Consider the function 10, 1, 5, with two differences $(1, -9)$ and $(2, 4)$. After advancing this one step, the new function is 10, 10, 5, so there is now a single difference $(2, -5)$. If we keep track of when and where these collisions take place, we can make changes to the structure accordingly.

The structure of choice here is a treap of differences. When we add two functions, we insert all elements of the smaller treap into the larger one; a standard argument shows that at most $O(k \log k)$ insertions will take place overall. To keep track of collisions, we'll have to maintain collision times for all adjacent border pairs, and store the minimal value in the root of each subtree. This may seem cumbersome, but every adjacent pair of elements occurs either as (the rightmost safe-house in the left subtree of $v$, $v$), or ($v$, the leftmost safe-house in the right subtree of $v$), hence the standard $relax$ function in the treap implementation can handle this.

One further detail is that we don't want to change the time values in our treaps. Instead, we'll use "lazy" time shifting, that is, we'll keep an additional value $\Delta$ associated with each treap, and assume that for entries $(t, d)$ with $d > 0$ the actual time should be $t - \Delta$, and with $d < 0$ the time should be $t + \Delta$. This way, we won't need to actually change anything in the treap when advancing (apart from resolving collisions).

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, ans, s;
vector<pair<int, int>> graph[N], q[N];
struct node {
    int t;
    map<int, int> f, g;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    void update(int x, int v) {
    if (v == 1) {
        auto it = g.upper_bound(x - 2 * t);
        if (it != g.begin())
            pq.emplace(x - prev(it)->first, x);
    } else {
        auto it = f.lower_bound(x + 2 * t);
        if (it != f.end())
            pq.emplace(it->first - x, it->first);
    }
}

    void cal(int d) {
    while (pq.size() && pq.top().first <= 2 * (t + d)) {
        int x = pq.top().second, y = pq.top().second - pq.top().first;
        pq.pop();
        auto ix = f.find(x), iy = g.find(y);
        if (ix == f.end() || iy == g.end())
            continue;
        if (ix->second + iy->second < 0) {
            iy->second += ix->second;
            f.erase(ix);
            update(iy->first, -1);
        } else {
            ix->second += iy->second;
            g.erase(iy);
            update(ix->first, 1);
        }
    }
    t += d;
}

    void add(int p, int x) {
    if (x > 0) {
        f[p + t] += x;
        update(p + t, 1);
    } else {
        g[p - t] += x;
        update(p - t, -1);
    }
}

    int ask(int p) {
    int s = 0;
    if (f.find(p + t) != f.end())
        s += f[p + t];
    if (g.find(p - t) != f.end())
        s += g[p - t];
    return s;
}

    int sz() {
    return f.size() + g.size();
}

};
node dp[N];
map<int, int> mp;
void merge(node &a, node &b) {
    if (a.sz() < b.sz())
        swap(a, b);
    for (auto [d, x]: b.f)
        a.add(d - b.t, x);
    for (auto [d, x]: b.g)
        a.add(d + b.t, x);
}
void dfs(int u, int f) {
    for (auto [v, w]: graph[u]) {
        if (v == f)
            continue;
        dfs(v, u);
        for (auto &[d, x]: q[v])
            x -= max(0, max(-dp[v].ask(d), dp[v].ask(d + 1)));
        dp[v].cal(1);
        for (auto [d, x]: q[v])
            if (x > 0)
                dp[v].add(d, x), dp[v].add(d + 1, -x);
        dp[v].cal(w - 1);
        merge(dp[u], dp[v]);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w * 2);
        graph[v].emplace_back(u, w * 2);
    }
    n++;
    graph[n].emplace_back(1, 2);
    graph[1].emplace_back(n, 2);
cin >> m ;
     for (int i = 1; i <= m; i++) {
        int d, x, u;
        cin >> d >> x >> u;
        q[u].emplace_back(d * 2, x);
    }
    dfs(n, 0);
     for (auto [d, x]: dp[n].f){
        mp[d - dp[n].t] += x;
    }
    for (auto [d, x]: dp[n].g){
        mp[d + dp[n].t] += x;
    }
     for (auto i: mp) {
        s += i.second;
        ans = max(ans, s);
    }
    cout << ans << '\n';
    return 0;
}