#include "infection.h"
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>

using namespace std;
typedef long long ll;

const int N = 150000 + 7;

vector<int> g[N];
int sz[N], p[N];

void hld_reorder(int v, int pr) {
    sz[v] = 1;
    p[v] = pr;

    for (int i = 0; i < g[v].size(); ++i) {
        if (g[v][i] == p[v]) {
            g[v].erase(g[v].begin() + i);
            break;
        }
    }

    for (int u : g[v]) {
        hld_reorder(u, v);
        sz[v] += sz[u];
    }

    sort(g[v].begin(), g[v].end(), [&](int x, int y) {
        return sz[x] > sz[y];
    });
}

int tim = 0;
int tin[N], tout[N], h[N], st[N];
void dfs(int v, int s) {
    st[v] = s;
    tin[v] = tim++;
    h[v] = h[p[v]] + 1;

    if (!g[v].empty()) {
        dfs(g[v][0], s);
    }
    for (int i = 1; i < g[v].size(); ++i) {
        dfs(g[v][i], g[v][i]);
    }
    tout[v] = tim;
}

ll get(int x, int y){
    ll ans = 0;
    while (st[x] != st[y]) {
        if (h[st[x]] > h[st[y]]) {
            ans += h[x];
            x = p[st[x]];
            ans -= h[x];
        }
        else {
            ans += h[y];
            y = p[st[y]];
            ans -= h[y];
        }
    }
    ans += abs(h[x] - h[y]);
    return ans;
}

int pre[N];
void walk(int v, int p) {
    pre[v] = p;
    for (int u : g[v]) {
        if (u == p) continue;
        walk(u, v);
    }
}

struct event {
    int tm, v, u, tp;
    event(int tm_, int v_, int u_, int tp_) {
        tm = tm_;
        v = v_;
        u = u_;
        tp = tp_;
    }
};

bool operator<(const event &a, const event &b) {
    if (a.tm != b.tm) return a.tm < b.tm;
    if (a.tp != b.tp) return a.tp > b.tp;
    if (a.v != b.v) return a.v < b.v;
    return a.u < b.u;
}

std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<ll> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
) 
{
    for (int i = 0; i < R.size(); ++i) {
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }

    int n = R.size();
    ++n;
    int q = S.size();

    
    /*
    hld_reorder(0, 0);
    h[0] = -1;
    dfs(0, 0);
    */

    set<pair<int, int>> s[2][2][2];

    vector<bool> c(q);
    vector<bool> d(q);
    vector<bool> good(q, true);


    auto add = [&](int i) {
        s[c[i]][d[i]][I[i]].insert({ S[i], i });
        good[i] = true;
    };
    auto del = [&](int i) {
        s[c[i]][d[i]][I[i]].erase({ S[i], i });
        good[i] = false;
    };

    for (int i = 0; i < q; ++i) {
        c[i] = S[i] % 2;
        d[i] = S[i] < T[i];
        add(i);
    }
    
    set<event> evs;
    for (int i = 0; i < q; ++i) {
        evs.insert(event(abs(T[i] - S[i]) + D[i], i, i, -1));
    }

    auto next = [&](int i) {
        if (d[i]) {
            auto it = s[c[i]][0][!I[i]].lower_bound({ S[i], -1 });
            if (it == s[c[i]][0][!I[i]].end()) {
                return -1;
            }
            int j = it->second;
            return j;
        }
        else {
            auto it = s[c[i]][1][!I[i]].lower_bound({ S[i], q + 1 });
            if (it == s[c[i]][1][!I[i]].begin()) {
                return -1;
            }
            --it;
            int j = it->second;
            return j;
        }
    };


    auto upd = [&](int i) {
        int j = next(i);
        if (j == -1) return;
        evs.insert(event((D[i] + D[j] + abs(S[j] - S[i])) / 2, i, j, 1));
    };
   
    for (int i = 0; i < q; ++i) {
        upd(i);
    }

    vector<int> ans(q, 0);
    for (int i = 0; i < q; ++i) {
        if (I[i]) {
            ans[i] = D[i];
        }
    }

    while (!evs.empty()) {
        event ev = *evs.begin();
        evs.erase(evs.begin());

        if (ev.tp == -1) {
            int j = next(ev.v);
            if (j != -1) {
                add(j);
            }
            del(ev.v);
        }
        if (ev.tp == 1) {
            if (!good[ev.u] || !good[ev.v]) continue;
            if (I[ev.v] == I[ev.u]) continue;
            if (I[ev.v]) swap(ev.v, ev.u);
            
            del(ev.v);

            ans[ev.v] = ev.tm;
            I[ev.v] = true;

            add(ev.v);

            upd(ev.v);
            upd(ev.u);
        }
    }

    for (int i = 0; i < q; ++i) {
        ans[i] = abs(T[i] - S[i]) + D[i] - ans[i] + 1;
        if (!I[i]) {
            ans[i] = 0;
        }
    }
    return ans;
}
