#include "bits/stdc++.h"
#include "infection.h"

using namespace std;

vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {
    int n = R.size() + 1;
    vector<int> g[n];
    for (auto [u, v] : R) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<vector<int> > up(20, vector<int>(n));
    vector<int> dist(n), tin(n), tout(n);
    int timer = 0;
    function<void(int)> dfs = [&](int v) {
        dist[v] = dist[up[0][v]] + 1;
        tin[v] = ++timer;
        for (int i = 1; i < 20; i++) up[i][v] = up[i - 1][up[i - 1][v]];
        for (int to : g[v]) {
            if (to != up[0][v]) up[0][to] = v, dfs(to);
        }
        tout[v] = timer;
    };
    dfs(0);
    auto upper = [&](int u, int v) {
        return tin[u] <= tin[v] and tout[v] <= tout[u];
    };

    auto lca = [&](int u, int v) {
        if (upper(u, v)) return u;
        if (upper(v, u)) return v;
        for (int i = 19; i >= 0; i--) {
            if (!upper(up[i][u], v)) u = up[i][u];
        }
        return up[0][u];
    };

    auto dis = [&](int u, int v) {
        return dist[u] + dist[v] - dist[lca(u, v)] * 2;
    };

    int m = (int)D.size();
    vector<int> ans(m);
    for (int i = 0; i < m; i++) ans[i] = (dis(S[i], T[i]) + 1) * I[i];
    return ans;
}
