#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
std::vector<int> solve(
std::vector<std::pair<int, int>> R,
std::vector<long long> D,
std::vector<int> S,
std::vector<int> T,
std::vector<bool> I
) {
    for (auto &[i, j] : R) i++, j++;
    for (auto &i : S) i++;
    for (auto &i : T) i++;
    long long n = R.size() + 1;
    vector<long long> g[n + 1];
    for (auto [i, j] : R) {
        g[i].push_back(j);
        g[j].push_back(i);
    }
    vector<long long> tin(n + 3), tout(n + 3);
    long long timer = 0;
    vector<vector<long long>> up(20, vector<long long>(n + 3));
    function<void(long long, long long)> dfs = [&](long long v, long long p) {
        tin[v] = timer++;
        up[0][v] = p;
        for (long long lg = 1; lg < 20; ++lg) {
            up[lg][v] = up[lg - 1][up[lg - 1][v]];
        }
        for (auto to : g[v]) {
            if (to == p) continue;
            dfs(to, v);
        }
        tout[v] = timer++;
        return;
    };
    dfs(1, 0);
    auto parent = [&](long long u, long long v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    };
    auto lca = [&](long long u, long long v) {
        if (parent(u, v)) return u;
        if (parent(v, u)) return v;
        for (long long lg = 19; lg >= 0; --lg) {
            if (up[lg][u] != 0 && parent(up[lg][u], v) == false) {
                u = up[lg][u];
            }
        }
        return up[0][u];
    };
    cc_hash_table<long long, vector<pair<long long, long long>>> mp;
    long long m = S.size();
    vector<int> ans(m);
    for (long long i = 0; i < m; ++i) {
        long long st = S[i], fn = T[i];
        int l = lca(u, v);
        vector<int> way, tmp;
        while (true) {
            way.push_back(st);
            if (st == l) break;
            st = up[0][st];
        }
        while (true) {
            if (fn == l) break;
            tmp.push_back(fn);
            fn = up[0][fn];
        }
        reverse(tmp.begin(), tmp.end());
        for (auto j : tmp) way.push_back(j);
        for (long long j = 0; j < len; ++j) {
            mp[j + D[i]].push_back({way[j], i});
        }
    }

    for (auto [key, vec] : mp) {
        long long sum = 0;
        map<long long, bool> mapa;
        for (auto [ver, idx] : vec) {
            mapa[ver] = mapa[ver] | I[idx];
        }
        for (auto [ver, idx] : vec) {
            if (mapa[ver]) I[idx] = true;
            ans[idx] += I[idx];
        }
    }
    return ans;
}
