#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<int>> gr;
vector<int> tin, tout, d, p;
vector<vector<pair<int, int>>> onLay;
int timer = 0;

void dfs(int u, int pp, int dd) {
    tin[u] = timer++;
    d[u] = dd;
    p[u] = pp;
    onLay[dd].emplace_back(tin[u], u);
    for (int v : gr[u]) {
        if (v != pp) {
            dfs(v, u, dd + 1);
        }
    }
    tout[u] = timer++;
}

bool isParent(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

vector<int> solve(vector<pair<int, int>> edgs, vector<ll> dd, vector<int> s, vector<int> t, vector<bool> infected) {
    int n = edgs.size() + 1;
    gr.resize(n);
    tin.resize(n);
    tout.resize(n);
    d.resize(n);
    onLay.resize(n);
    p.resize(n);
    for (auto [u, v] : edgs) {
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    int m = dd.size();
    dfs(0, -1, 0);
    vector<ll> ans(m, 1000000000000000000);
    vector<pair<ll, int>> joinTm(m);
    for (int i = 0; i < m; ++i) {
        joinTm[i] = {dd[i], i};
    }
    sort(joinTm.begin(), joinTm.end());
    set<int> in;
    // set<int> cur_inf, cur_not_inf;
    vector<int> whr(m);
    ll tm = 0;
    int ind = 0;
    auto getCorrectSon = [&](int u, int v) {
        assert(isParent(u, v) && u != v);
        auto it = prev(lower_bound(onLay[d[u] + 1].begin(), onLay[d[u] + 1].end(), make_pair(tin[v], 1000000000)));
        return it->second;
    };
    vector<ll> hasInf(n, -1);
    vector<int> ansFinale(m);
    while (true) {
        while (ind != m && joinTm[ind].first == tm) {
            in.insert(joinTm[ind].second);
            whr[joinTm[ind].second] = s[joinTm[ind].second];
            if (infected[joinTm[ind].second]) {
                ans[joinTm[ind].second] = tm;
            }
            // if (infected[joinTm[ind].second]) {
            //     cur_inf.insert(joinTm[ind].second);
            // } else {
            //     cur_not_inf.insert(joinTm[ind].second);
            // }
            ind++;
        }
        if (in.empty()) {
            if (ind == m) {
                break;
            }
            tm = joinTm[ind].first;
            continue;
        }
        for (int i : in) {
            if (infected[i]) {
                hasInf[whr[i]] = tm;
            }
        }
        for (int i : in) {
            if (!infected[i] && hasInf[whr[i]] == tm) {
                infected[i] = true;
                ans[i] = tm;
            }
        }
        vector<int> toRem;
        for (int i : in) {
            if (whr[i] == t[i]) {
                ansFinale[i] = ans[i] == 1000000000000000000 ? 0 : (tm - ans[i] + 1);
                toRem.push_back(i);
            }
        }
        for (int i : toRem) {
            in.erase(i);
        }
        for (int i : in) {
            int u = whr[i];
            if (isParent(u, t[i])) {
                whr[i] = getCorrectSon(u, t[i]);
            } else {
                whr[i] = p[u];
            }
        }
        tm++;
    }
    return ansFinale;
}