
#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);
    function<void(int)> dfs = [&](int ps) {
        for(int &to : g[ps]) {
            if(pr[to] || to == 0)continue;
            pr[to] = ps;
            dp[to] = dp[ps] + 1;
            dfs(to);
        }
    };
    dfs(0);

    int m = d.size();
    vector<array<ll,3>> que;
    vector<ll> ans(m, inf), len(m);
    for(int i = 0; i < m; i ++ ) {

        vector<int> v, v2;
        while(1) {
            if(s[i] == t[i]) {
                v.push_back(s[i]);
                break;
            }
            if(dp[s[i]] > dp[t[i]]) {
                v.push_back(s[i]);
                s[i] = pr[s[i]];
            }else {
                v2.push_back(t[i]);
                t[i] = pr[t[i]];
            };
        }
        reverse(v2.begin(), v2.end());
        for(int &i : v2)v.push_back(i);

        len[i] = v.size();
        for(int j = 0; j < v.size(); j ++ ) {
            que.push_back({d[i] + j, v[j], i});
        }
        if(k[i])ans[i] = d[i];
        else ans[i] = d[i] + len[i];
    }
    sort(que.rbegin(), que.rend());

    while(que.size()) {
        auto [x, y, z]  = que.back();
        que.pop_back();
        bool ok = (ans[z] <= x);
        vector<int> rs;
        rs.push_back(z);
        while(que.size() && que.back()[0] == x && que.back()[1] == y) {
            rs.push_back(que.back()[2]);
            ok |= (rs.back() <= x);
            que.pop_back();
        }
        if(ok) {
            for(int &i : rs)ans[i] = min(ans[i], x);
        }
    }

    for(int i = 0; i < m; i ++ ) {
        cout << len[i] - (ans[i] - d[i]) << '\n';
    }
}
