#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 150000 + 7;

vector<int> g[MAXN];
int dep[MAXN], jump[MAXN], par[MAXN];

void dfs(int u, int p = 0) {
    dep[u] = dep[p] + 1;
    for (auto v : g[u]) {
        if (v == p) continue;
        par[v] = u;
        if (dep[u] - dep[jump[u]] == dep[jump[u]] - dep[jump[jump[u]]]) {
            jump[v] = jump[jump[u]];
        } else {
            jump[v] = u;
        }
        dfs(v, u);
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    while (dep[a] > dep[b]) {
        if (dep[jump[a]] >= dep[b]) {
            a = jump[a];
        } else {
            a = par[a];
        }
    }
    while (a != b) {
        if (jump[a] != jump[b]) {
            a = jump[a], b = jump[b];
        } else {
            a = par[a], b = par[b];
        }
    }
    return a;
}

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

vector<int> solve(vector<pair<int, int>> R, vector<ll> D, vector<int> S, vector<int> T, vector<bool> I) {
    int n = R.size() + 1;
    int m = D.size();
    for (int i = 0; i < n - 1; ++i) {
        ++R[i].first, ++R[i].second;
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }
    for (int i = 0; i < m; ++i) ++S[i], ++T[i];
    vector<int> sol(m);
    dfs(1);
    for (int i = 0; i < m; ++i) {
        if (I[i] == 1) {
            sol[i] = dist(S[i], T[i]);
        }
    }
    for (int i = 1; i <= n; ++i) g[i].clear();
    return sol;
}