#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;

ll day[mxn];
int n, m, s[mxn], t[mxn], bad[mxn], dep[mxn], up[mxn][20];
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();
}

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<array<ll, 3> > ord;


    dfs(0, 0);
    for (int i=0; i<m; i++) {
        tour.clear();
        found = 0;
        dfs2(s[i], s[i], t[i]);

        for (int j=0; j<tuki.size(); j++)
            ord.push_back({ day[i]+j, tuki[j], i });
    }

    sort(ord.begin(), ord.end(), [&](array<ll, 3> x, array<ll, 3> y) {
        if (x[0] != y[0]) return x[0] < y[0];
        return bad[x[2]] > bad[y[2]];
    });

    vector<int> baba(n);
    int k = ord.size();

    int j = 0;
    for (int i=0; i<k; i=j+1) {
        j = i;
        while (j + 1 < k && ord[j+1][0] == ord[i][0]) j++;

        vector<int> vis(n);
        for (int x = i; x<=j; x++) {
            int id = ord[x][2];
            if (bad[id]) {
                vis[ord[x][1]] = 1;
            }
            if (vis[ord[x][1]]) {
                bad[id] = 1;
                ans[id] = max(ans[id], dist(ord[x][1], t[id]) + 1);
            }
        }
    }

    return ans;
}
