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

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)];
}

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];
    }

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

    return ans;
}
