#include "infection.h"
#include<bits/stdc++.h>
#define ll long long

using namespace std;

vector<vector<int> > g;

int nind(vector<ll>& tt, ll t) {
    return lower_bound(tt.begin(), tt.end(), t) - tt.begin();
}

bool dfs(int v, ll t2, int f, int p, vector<vector<pair<int, int> > >& t, int ind, vector<ll>& tt) {
    if (v == f) {
        t[nind(tt, t2)].push_back({v, ind});
        return true;
    }
    for (auto u : g[v]) {
        if (u != p) {
            bool res = dfs(u, t2 + 1, f, v, t, ind, tt);
            if (res) {
                t[nind(tt, t2)].push_back({v, ind});
                return true;
            }
        }
    }
    return false;
}

bool dfs2(int v, ll t2, int f, int p, int ind, vector<ll>& tt) {
    if (v == f) {
        tt.push_back(t2);
        return true;
    }
    for (auto u : g[v]) {
        if (u != p) {
            bool res = dfs2(u, t2 + 1, f, v, ind, tt);
            if (res) {
                tt.push_back(t2);
                return res;
            }
        }
    }
    return false;
}


std::vector<int> solve(
std::vector<std::pair<int, int>> R,
std::vector<long long> D,
std::vector<int> S,
std::vector<int> T,
std::vector<bool> I
) {
    int n = R.size() + 1;
    g = vector<vector<int> > (n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u = R[i].first;
        int v = R[i].second;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<ll> tt;
    for (int i = 0; i < S.size(); ++i) {
        dfs2(S[i], D[i], T[i], -1, i, tt);
    }
    sort(tt.begin(), tt.end());
    tt = vector<ll> (tt.begin(), unique(tt.begin(), tt.end()));
    /*for (auto i : tt) {
        cout << i << ' ';
    }
    cout << '\n';*/
    int mxt = tt.size();
    vector<vector<pair<int, int> > > t(mxt + 1);
    for (int i = 0; i < S.size(); ++i) {
        bool ts = dfs(S[i], D[i], T[i], -1, t, i, tt);
    }
    vector<int> ans(S.size());
    for (int i = 0; i < mxt + 1; ++i) {
        unordered_set<int> st;
        for (auto p : t[i]) {
            if (I[p.second]) {
                st.insert(p.first);
            }
        }
        for (auto p : t[i]) {
            if (st.count(p.first)) {
                I[p.second] = true;
                ans[p.second]++;
            }
        }
    }
    return ans;
}