#include "infection.h"
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"

using namespace std;
using namespace __gnu_pbds;

#define for0(i, n) for (ll i = 0; i < n; i++)
#define for1(i, n) for (ll i = 1; i < n; i++)
#define rfor0(i, n) for (ll i = n - 1; i >= 0; i--)
#define be(x) x.begin()
#define en(x) x.end()
#define all(x) be(x), en(x)
#define sz(x) x.size()
#define pb push_back
#define con continue
#define ret return

typedef long long ll;
typedef vector<ll> vll;

const ll N = 1.5e5 + 5, K = 18;

ll n, m, s[N], in[N], ou[N], ti, pr[N], hd[N], h[N], up[K][N];
vll g[N];

void dfs1(ll v, ll p) {
    up[0][v] = p;
    for1(i, K) up[i][v] = up[i - 1][up[i - 1][v]];
    pr[v] = p;
    s[v] = 1;
    if (v != p) g[v].erase(find(all(g[v]), p));
    for (auto x : g[v]) {
        if (x == p) con;
        h[x] = h[v] + 1;
        dfs1(x, v);
        s[v] += s[x];
    }
    sort(all(g[v]), [&](ll x, ll y) { ret s[x] > s[y]; });
}

void dfs2(ll v, ll hh) {
    in[v] = ti++;
    hd[v] = hh;
    for (auto x : g[v]) {
        dfs2(x, (x == g[v][0] ? hh : x));
    }
    ou[v] = ti;
}

bool is_p(ll u, ll v) {
    ret in[u] <= in[v] && ou[u] >= ou[v];
}

ll lca(ll u, ll v) {
    if (u == v) ret u;
    if (in[u] > in[v]) swap(u, v);
    rfor0(i, K) {
        if (!is_p(up[i][v], u)) v = up[i][v];
    }
    ret up[0][v];
}

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) {
    n = sz(R) + 1, m = sz(D);
    for0(i, n - 1) {
        auto [u, v] = R[i];
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs1(0, 0);
    dfs2(0, 0);
    vector<int> ans(m), used(m);
    map<int, cc_hash_table<int, null_type>> mm;
    vector<cc_hash_table<int, vector<int>>> ma(n);
    for0(i, m) {
        used[i] = I[i];
        int u = S[i], v = T[i], w = lca(u, v);
        int d = D[i];
        while (u != w) {
            mm[d].insert(u);
            ma[u][d].push_back(i);
            d++;
            u = up[0][u];
        }
        mm[d].insert(w);
        ma[w][d].push_back(i);
        d++;
        d += h[v] - h[w] - 1;
        while (v != w) {
            mm[d].insert(v);
            ma[v][d].push_back(i);
            d--;
            v = up[0][v];
        }
    }
    for (auto [d, b] : mm) {
        for (auto v : b) {
            auto A = ma[v][d];
            bool f = 0;
            for (auto i : A) {
                if (used[i]) f = 1;
            }
            if (f) {
                for (auto i : A) {
                    used[i] = 1;
                }
            }
            for (auto i : A) {
                ans[i] += used[i];
            }
        }
    }
    return ans;
}
