#include <bits/stdc++.h>

// meoowww mrrowww :3
// go play vivid/stasis!!! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = []{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    return 0;
}();

vector<int> adj[150000];
int par[150000][18];
int depth[150000];

void dfs1(int i = 0, int p = 0, int d = 0) {
    par[i][0] = p;
    fo(k, 1, 18) par[i][k] = par[par[i][k - 1]][k - 1];
    depth[i] = d;

    for (int j : adj[i]) {
        if (j == p) continue;
        dfs1(j, i, d + 1);
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);

    fo(k, 0, 18) if ((depth[b] - depth[a]) & (1 << k)) b = par[b][k];
    if (a == b) return a;

    of(k, 0, 18) if (par[a][k] != par[b][k]) a = par[a][k], b = par[b][k];
    return par[a][0];
}

int dist(int a, int b) {
    int c = lca(a, b);
    return depth[a] + depth[b] - 2 * depth[c];
}

vector<int> solve(vector<pair<int, int>> r, vector<long long> d, vector<int> s, vector<int> t, vector<bool> inf) {
    int n = r.size() + 1, m = d.size();
    fo(i, 0, n - 1) adj[r[i].f].pb(r[i].s), adj[r[i].s].pb(r[i].f);
    dfs1();

    vector<vector<int>> paths_for;
    fo(i, 0, m) {
        vector<int> path { t[i] };
        int c = lca(s[i], t[i]);
        while (path.back() != c) path.pb(par[path.back()][0]);
        reverse(be(path));
        paths_for.pb(path);
    }

    vector<int> res(m);
    
    map<long long, vector<pair<pair<int, bool>, int>>> to_go;
    fo(i, 0, m) {
        if (s[i] == lca(s[i], t[i])) to_go[d[i]].pb({ { 0, true }, i });
        else to_go[d[i]].pb({ { s[i], false }, i });
    }

    while (to_go.size()) {
        long long cd = to_go.begin()->f;
        vector<pair<pair<int, bool>, int>> curr = move(to_go[cd]);
        to_go.erase(cd);

        set<int> is_infected;
        for (auto [p, i] : curr) {
            if (inf[i]) is_infected.insert(p.s ? paths_for[i][p.f] : p.f);
        }

        for (auto [p, i] : curr) {
            if (is_infected.count(p.s ? paths_for[i][p.f] : p.f)) {
                res[i]++;
                inf[i] = true;
            }
        }

        for (auto [p, i] : curr) {
            if (p.s) {
                if (p.f + 1 < paths_for[i].size())
                    to_go[cd + 1].pb({ { p.f + 1, true }, i });
            } else {
                int j = par[p.f][0];
                if (paths_for[i][0] == j) to_go[cd + 1].pb({ { 0, true }, i });
                else to_go[cd + 1].pb({ { j, false }, i });
            }
        }
    }

    return res;
}