#include <bits/stdc++.h>

using namespace std;

const int N = 151000;

int n, ans[N];
bool bad[N];
vector<int> g[N], path;
map<int, vector<int>> mp;

bool dfs(int v, int t, int p = -1) {
    path.push_back(v);
    if (v == t) return true;
    for (int u : g[v])
        if (u != p && dfs(u, t, v))
            return true;
    path.pop_back();
    return false;
}

vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    n = (int) R.size() + 1;
    for (int i = 0; i < n - 1; i++) {
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }
    int m = I.size();
    for (int i = 0; i < m; i++) {
        path.clear();
        dfs(S[i], T[i]);
        for (int j = 0; j < (int) path.size(); j++) {
            mp[D[i] + j].push_back(path[j]);
            mp[D[i] + j].push_back(i);
        }
    }
    for (auto &[dd, vv] : mp) {
        for (int i = 0; i < (int) vv.size(); i += 2) {
            int u = vv[i + 0];
            int v = vv[i + 1];
            if (I[v]) bad[u] = true;
        }
        for (int i = 0; i < (int) vv.size(); i += 2) {
            int u = vv[i + 0];
            int v = vv[i + 1];
            if (bad[u]) {
                I[v] = true;
                ans[v]++;
            }
        }
        for (int i = 0; i < (int) vv.size(); i += 2) {
            int u = vv[i + 0];
            int v = vv[i + 1];
            bad[u] = false;
        }
    }
    vector<int> fin(m);
    for (int i = 0; i < m; i++)
        fin[i] = ans[i];
    return fin;
}
