#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mxn = 1.5e5 + 5;

struct segment_tree {
    int n;
    vector<int> tree;

    void init(int _n) {
        n = _n;
        tree.resize(4*n, 1e9);
    }

    void update(int u, int tl, int tr, int p, int v) {
        if (tl == tr) {
            tree[u] = min(tree[u], v);
        } else {
            int tm = (tl + tr) / 2;
            if (p <= tm) update(2*u, tl, tm, p, v);
            else update(2*u+1, tm+1, tr, p, v);
            tree[u] = min(tree[2*u], tree[2*u+1]);
        }
    }

    int query(int u, int tl, int tr, int l, int r) {
        if (tl > r || l > tr) return 1e9;
        if (l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return min ( query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int p, int v) {
        update(1, 0, n-1, p, v);
    }

    int query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }
};

ll day[mxn];
int n, m, s[mxn], t[mxn], bad[mxn], dep[mxn], up[mxn][20], prec[5005][5005];
vector<int> g[mxn], tour, tuki;
set<ll> st[mxn];
int found = 0;

void dfs(int u, int p) {
    for (int i=1; i<20; i++)
            up[u][i] = up[up[u][i-1]][i-1];

    for (int v : g[u]) if (v ^ p) {
        dep[v] = dep[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
}

int jmp(int u, int d) {
    for (int i=0; i<20; i++)
        if (d & (1 << i)) u = up[u][i];
    return u;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    a = jmp(a, dep[a] - dep[b]);
    if (a == b) return a;
    for (int i=19; i>=0; i--) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

int dist(int a, int b) {
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}

void dfs2(int u, int p, int t) {
    if (found) return ;
    tour.push_back(u);
    if (u == t) {
        tuki = tour;
        found = 1;
        return ;
    }

    for (int v : g[u]) if (v ^ p) dfs2(v, u, t);

    tour.pop_back();
}

void dfs3(int u, int p, int d, int s) {
    prec[s][u] = d;
    for (int v : g[u]) if (v ^ p)
        dfs3(v, u, d + 1, s);
}

vector<int> solve(
    vector<pii> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {
    n = R.size() + 1;
    m = D.size();
    vector<int> ans(m);

    for (int i=0; i<n-1; i++) {
        auto [u, v] = R[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i=0; i<m; i++) {
        day[i] = D[i];
        s[i] = S[i];
        t[i] = T[i];
        bad[i] = I[i];
    }

    vector<int> bad_at(n);
    for (int i=0; i<m; i++)
        if (bad[i]) bad_at[s[i]] = 1;

    for (int i=0; i<m; i++) {
        if (bad_at[i]) ans[i] = abs(s[i]-t[i]) + 1, bad[i] = i;
    }

    vector<pii> ord1[2], ord2[n];
    set<int> st[2];

    for (int i=0; i<m; i++) {
        if (s[i] == t[i]) continue;
        if (s[i] < t[i]) {
            ord1[s[i]&1].push_back({ s[i], i });
        } else if (bad[i]) {
            ord2[s[i]&1].push_back({ 2*t[i] - s[i], i });
        }
    }

    for (int t=0; t<2; t++) {
        sort(ord1[t].begin(), ord1[t].end());
        sort(ord2[t].begin(), ord2[t].end());

        int j = 0;
        for (auto [v, i] : ord1[t]) {
            while (j < ord2[t].size() && ord2[t][j].first <= v) {
                st[t].insert(s[ord2[t][j].second]);
                j++;
            }

            auto it = st[t].lower_bound(s[i]);
            if (it != st[t].end() && *it <= 2*T[i]-s[i]) {
                int p = (s[i] + *it) / 2;
                ans[i] = max(ans[i], T[i] - p + 1);
            }
        }

        ord1[t].clear();
        ord2[t].clear();
        st[t].clear();
    }

    for (int i=0; i<m; i++) {
        if (s[i] == t[i]) continue;
        if (s[i] > t[i]) {
            ord1[s[i]&1].push_back({ s[i], i });
        } else if (bad[i]) {
            ord2[s[i]&1].push_back({ 2*t[i]-s[i], i });
        }
    }

    for (int t=0; t<2; t++) {
        sort(ord1[t].rbegin(), ord1[t].rend());
        sort(ord2[t].rbegin(), ord2[t].rend());

        int j = 0;
        for (auto [v, i] : ord1[t]) {
            while (j < ord2[t].size() && ord2[t][j].first >= v) {
                st[t].insert(s[ord2[t][j].second]);
                j++;
            }

            if (st[t].empty()) continue;
            if (*st[t].begin() > s[i]) continue;

            auto it = --st[t].upper_bound(s[i]);

            if (it != st[t].end() && 2*T[i]-s[i] <= *it) {
                int p = (*it + s[i]) / 2;
                ans[i] = max(ans[i], p - T[i] + 1);
            }
        }
    }

    return ans;
}
