#include<bits/stdc++.h>

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

const int N = 5000;
int who[N][N];

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<int> psz(m);
    std::vector<std::pair<std::pair<ll, int>, int>> states;
    states.reserve(n * m);
    std::vector<int> p1;
    for (int i = 0; i < m; ++i) {
        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;
        };
        p1.clear();
        dfs(dfs, s[i], -1);
        psz[i] = p1.size();
        for (int j = 0; j < p1.size(); ++j) {
            states.push_back({{d[i] + j, p1[j]}, i});
        }
    }
    std::vector<int32_t> ans(m, n + 1);
    std::sort(states.begin(), states.end());
    for (int i = 0; i < states.size(); ) {
        int j = i;
        while (j < states.size() && states[i].first == states[j].first) {
            int k = states[j].second;
            who[k][states[i].first.first - d[k]] = i;
            ++j;
        }
        i = j;
    }
    std::vector<int> ptr(states.size()), ptrp(m);
    std::iota(ptr.begin(), ptr.end(), 0);
    auto fst = [&](int i) -> int {
        while (ptr[i] < states.size() && states[ptr[i]].first == states[i].first && ans[states[ptr[i]].second] <= n) ++ptr[i];
        return ptr[i] < states.size() && states[ptr[i]].first == states[i].first ? states[ptr[i]].second : -1;
    };
    auto infect = [&](int i, ll t) -> void {
        ans[i] = t - d[i];
        ptrp[i] = ans[i];
    };
    auto get = [&](int i) -> std::pair<int, ll> {
        while (ptrp[i] < psz[i]) {
            int k = fst(who[i][ptrp[i]]);
            if (k != -1) return {k, d[i] + ptrp[i]};
            ++ptrp[i];
        }
        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] < psz[i]) ans[i] = psz[i] - ans[i];
        else ans[i] = 0;
    }
    return ans;
}