#include<bits/stdc++.h>

using ll = long long;
const ll inf = 1e18;

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();
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        auto [u, v] = R[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    std::vector<std::vector<int>> path(m);
    std::vector<std::pair<ll, int>> states;
    states.reserve(n * m);
    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) {
            states.emplace_back(d[i] + j, path[i][j]);
        }
    }
    std::vector<int32_t> ans(m, n + 1);
    std::sort(states.begin(), states.end());
    states.resize(std::unique(states.begin(), states.end()) - states.begin());
    std::vector<std::vector<int>> who(states.size());
    std::vector<int> ptr(states.size());
    auto fst = [&](int i) -> int {
        while (ptr[i] < who[i].size() && ans[who[i][ptr[i]]] <= n) ++ptr[i];
        return ptr[i] < who[i].size() ? who[i][ptr[i]] : -1;
    };
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < path[i].size(); ++j) {
            path[i][j] = std::lower_bound(states.begin(), states.end(), std::pair{d[i] + j, path[i][j]}) - states.begin();
            who[path[i][j]].push_back(i);
        }
    }
    auto infect = [&](int i, ll t) -> void {
        ans[i] = t - d[i];
    };
    auto get = [&](int i) -> std::pair<int, ll> {
        for (int j = ans[i]; j < path[i].size(); ++j) {
            int k = fst(path[i][j]);
            if (k != -1) return {k, 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] < path[i].size()) ans[i] = path[i].size() - ans[i];
        else ans[i] = 0;
    }
    return ans;
}