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

const int K = 300;

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];
    dfs(1);
    vector<int> sol(m);
    
    vector<array<int, 3>> events;
    for (int i = 0; i < m; ++i) {
        int c = lca(S[i], T[i]);
        int u = S[i];
        int timp = D[i];
        int bulan = 0;
        while (u != c) {
            events.push_back({timp, u, i});
            ++timp;
            u = par[u];
            ++bulan;
            if (bulan > K) break;
        }
        bulan = 0;
        events.push_back({timp, c, i});
        timp = D[i] + dist(S[i], T[i]);
        u = T[i];
        while (u != c) {
            events.push_back({timp, u, i});
            --timp;
            u = par[u];
            ++bulan;
            if (bulan > K) break;
        }
    }
    sort(events.begin(), events.end());
    // for (int i = 0; i < events.size(); ++i) {
    //     if (i == 0 || events[i][0] != events[i - 1][0]) {
    //         cout << "\n";
    //     }
    //     cout << events[i][0] << " " << events[i][1] << " " << events[i][2] << "\n";
    // }

    vector<int> day(m, -1);
    int i = 0;
    while (i < events.size()) {
        int j = i;
        while (j < events.size() && events[j][0] == events[i][0]) {
            ++j;
        }
        int k = i;
        while (k < j) {
            int p = k;
            while (p < j && events[p][1] == events[k][1]) ++p;
            bool inf = 0;
            // if (events[i][0] == 6) {
            //     cout << "! ";
            //     for (int it = k; it < p; ++it) {
            //         cout << events[it][1] << " ";
            //     }
            //     cout << "\n";
            // }
            for (int it = k; it < p; ++it) {
                if (day[events[it][2]] != -1 || I[events[it][2]] == 1) {
                    inf = 1;
                }
            }
            // if (events[i][0] == 6) {
            //     cout << inf << "\n";
            // }
            if (inf) {
                for (int it = k; it < p; ++it) {
                    if (day[events[it][2]] == -1) {
                        day[events[it][2]] = events[i][0];
                    }
                }
            }
            k = p;
        }
        i = j;
    }
    // for (int i = 0; i < m; ++i) {
    //     cout << i << ": " << day[i] << "\n";
    // }
    for (int i = 0; i < m; ++i) {
        if (day[i] == -1) {
            sol[i] = 0;
        } else {
            sol[i] = D[i] + dist(S[i], T[i]) - day[i] + 1;
        }
    }

    for (int i = 1; i <= n; ++i) g[i].clear();
    return sol;
}