
#include <bits/stdc++.h>
#include "infection.h"
//#include "grader.cpp"

using namespace std;

typedef long long ll;
ll inf = 1e18;

vector<int> solve(
    vector<pair<int, int>> r,
    vector<long long> d,
    vector<int> s,
    vector<int> t,
    vector<bool> k
) {

    int n = r.size() + 1;

    vector<vector<int>> g(n);
    for(auto &[x, y] : r) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> pr(n), dp(n), tin(n),tout(n);
    vector<vector<int>> ls(n, vector<int> (22));
    function<void(int)> dfs = [&](int ps) {
        ls[ps][0] = pr[ps];
        for(int i = 1; i < 22; i ++ )
            ls[ps][i] = ls[ls[ps][i-1]][i-1];

        for(int &to : g[ps]) {
            if(pr[to] || to == 0)continue;
            pr[to] = ps;
            dp[to] = dp[ps] + 1;
            dfs(to);
        }
    };
    dfs(0);

    auto lca = [&](int a, int b) {
        if(tin[a] <= tin[b] && tout[b] <= tout[a]) return a;
        if(tin[b] <= tin[a] && tout[a] <= tout[b]) return b;
        for(int i = 21; i >= 0; i -- ) {
            int na = ls[a][i];
            if(tin[na] <= tin[b] && tout[b] <= tout[na]) continue;
            a = na;
        }
        return ls[a][0];
    };

    int m = d.size();
    vector<int> ans(m);
    for(int i = 0; i < m; i ++ ) {

        int lc = lca(s[i], t[i]);
        int ds = dp[s[i]] + dp[t[i]] - dp[lc]*2;
        if(k[i])ans[i] = ds+1;
        else ans[i] = 0;
    }


    return ans;
}
