#include "infection.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define int long long

using namespace std;

using pii = pair<int, int>;

const int LOG = 19;

void dfsp(int v, int p, vector<vector<int>> &g, vector<int> &par, vector<int> &dep) {
    par[v] = p;
    for (int u : g[v]) {
        if (u != p) {
            dep[u] = dep[v] + 1;
            dfsp(u, v, g, par, dep);
        }
    }
}

int dist(int x, int y, vector<vector<int>> &binup, vector<int> &dep) {
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    int ans = 0;
    for (int b = LOG - 1; b >= 0; b--) {
        if (binup[b][y] != -1 && dep[binup[b][y]] >= dep[x]) {
            y = binup[b][y];
            ans += (1 << b);
        }
    }
    if (x == y) {
        return ans;
    }
    for (int b = LOG - 1; b >= 0; b--) {
        if (binup[b][x] != binup[b][y]) {
            x = binup[b][x]; y = binup[b][y];
            ans += (2 << b);
        }
    }
    return ans + 2;
}

vector<signed> solve(vector<pair<signed, signed>> R, vector<long long> D, vector<signed> S,
        vector<signed> T, vector<bool> I) {
    int n = R.size() + 1, m = D.size();
    vector<vector<int>> g(n);
    for (auto [x, y] : R) {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<vector<int>> binup(LOG, vector<int>(n));
    vector<int> dep(n);
    dfsp(0, -1, g, binup[0], dep);
    for (int b = 1; b < LOG; b++) {
        for (int i = 0; i < n; i++) {
            if (binup[b - 1][i] == -1) binup[b][i] = -1;
            else binup[b][i] = binup[b - 1][binup[b - 1][i]];
        }
    }

    vector<signed> ans(m);
    for (int i = 0; i < m; i++) {
        ans[i] = I[i] * (dist(S[i], T[i], binup, dep) + 1);
    }

    return ans;
}
