//#include "infection.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 150'002, LOG = 19;
int n, m, up[MAXN][LOG], depth[MAXN];
vector<int> adj[MAXN], infected[MAXN];

void dfs_lca(int u, int p = 0, int d = 0) {
    up[u][0] = p;
    depth[u] = d;
    for (int i = 1; i < LOG; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v: adj[u]) {
        if (v != p) dfs_lca(v, u, d + 1);
    }
}

int get_dist_and_track_infectivity(int u, int v, bool is_infected) {
    if (depth[u] < depth[v]) swap(u, v);
    int dist = 0;
    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[u][i];
            if (is_infected && (infected[u].empty() || infected[u].back() != i)) infected[u].emplace_back(i);
            ++dist;
        }
    }
    if (u == v) return dist;
    for (int i = LOG - 1; i >= 0; --i) {
        if (is_infected && (infected[u].empty() || infected[u].back() != i)) infected[u].emplace_back(i);
        if (is_infected && (infected[v].empty() || infected[v].back() != i)) infected[v].emplace_back(i);
        dist += 2;
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return dist;
}

int get_uninfected_dist(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int dist = 0;
    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[u][i];
            if (find(infected[u].begin(), infected[u].end(), i) != infected[u].end()) return dist;
            ++dist;
        }
    }
    if (u == v) return dist;
    for (int i = LOG - 1; i >= 0; --i) {
        if (find(infected[u].begin(), infected[u].end(), i) != infected[u].end()) return dist;
        dist += 2;
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
}

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 = R.size() + 1;
    m = D.size();

    for (const auto &[u, v]: R) {
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        adj[u].reserve(n);
        adj[v].reserve(n);
    }

    dfs_lca(1, 0, 0);

    vector<int> days_infected(n);
    for (int i = 0; i < m; ++i) days_infected[i] = get_dist_and_track_infectivity(S[i], T[i], I[i]);
    for (int i = 0; i < m; ++i) days_infected[i] -= get_uninfected_dist(S[i], T[i]);

    return days_infected;
}

// find min paths
// move 1 at a time
// check infectivity and update