#include<bits/stdc++.h>

using ll = long long;
#define int ll
const ll inf = 1e18;

const int N = 1.5e5;
const int LOG = 20;
std::vector<int> adj[N];
int bp[LOG][N], tin[N], tout[N];

int timer = 0;
void dfs(int u, int p) {
    tin[u] = timer++;
    bp[0][u] = p;
    for (int k = 0; k + 1 < LOG; ++k){
        if (bp[k][u] == -1) bp[k + 1][u] = -1;
        else bp[k + 1][u] = bp[k][bp[k][u]];
    }
    for (auto to : adj[u]) {
        if (to != p) {
            dfs(to, u);
        }
    }
    tout[u] = timer - 1;
}
bool is_par(int p, int u) {
    return tin[p] <= tin[u] && tout[u] <= tout[p];
}
int lca(int u, int v) {
    if (is_par(u, v)) return u;
    if (is_par(v, u)) return v;
    for (int k = LOG - 1; k >= 0; --k) {
        if (bp[k][u] != -1 && !is_par(bp[k][u], v)) u = bp[k][u];
    }
    return bp[0][u];
}


std::vector<int32_t> solve(std::vector<std::pair<int32_t, int32_t>> R, std::vector<ll> d, std::vector<int32_t> s, std::vector<int32_t> t, std::vector<bool> I) {
    int n = R.size() + 1;
    int m = d.size();
    for (int i = 0; i < n - 1; ++i) {
        auto [u, v] = R[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0, -1);
    std::vector<std::vector<int>> path(m);
    std::vector<std::map<ll, std::set<int>>> who(n);
    for (int i = 0; i < m; ++i) {
        std::vector<int> p1;
        auto dfs = [&](auto dfs, int u, int p) -> bool {
            p1.push_back(u);
            if (u == t[i]) return true;
            for (auto to : adj[u]) {
                if (to != p) {
                    if (dfs(dfs, to, u)) return true;
                }
            }
            p1.pop_back();
            return false;
        };
        dfs(dfs, s[i], -1);
        path[i] = p1;
        for (int j = 0; j < path[i].size(); ++j) {
            who[path[i][j]][d[i] + j].insert(i);
        }
    }
    std::vector<int32_t> ans(m, n + 1);
    auto infect = [&](int i, ll t) -> void {
        assert(ans[i] == n + 1);
        assert(0 <= t - d[i] && t - d[i] < path[i].size());
        ans[i] = t - d[i];
        for (int j = 0; j < path[i].size(); ++j) {
            who[path[i][j]][d[i] + j].erase(i);
        }
    };
    auto get = [&](int i) -> std::pair<int, ll> {
        for (int j = ans[i]; j < path[i].size(); ++j) {
            if (who[path[i][j]][d[i] + j].size()) return {*who[path[i][j]][d[i] + j].begin(), d[i] + j};
        }
        return {-1, inf};
    };
    std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<>> pq;
    for (int i = 0; i < m; ++i) {
        if (I[i]) {
            infect(i, d[i]);
            pq.emplace(get(i).second, i);
        }
    }
    while (pq.size()) {
        auto [_t, i] = pq.top();
        pq.pop();
        while (_t < inf) {
            auto [u, t] = get(i);
            if (t == _t) {
                infect(u, t);
                pq.emplace(get(u).second, u);
            } else {
                pq.emplace(t, i);
                break;
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        if (ans[i] <= n) ans[i] = path[i].size() - ans[i];
        else ans[i] = 0;
    }
    for (int i = 0; i < n; ++i){
        adj[i].clear();
    }
    timer = 0;
    return ans;
}