#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 150009, logMaxN = 18;
using ll = long long;
vector<int> adj[maxN];
int depth[maxN], par[maxN];
int sp[logMaxN][maxN];
bitset<maxN> vis;

void dfs(int cur) {
    vis[cur] = true;
    for (int son : adj[cur]) {
        if (!vis[son]) {
            par[son] = cur;
            depth[son] = depth[cur] + 1;
            dfs(son);
        }
    }
}
void initSp(int n) {
    for (int i = 0; i < n; i++) { sp[0][i] = par[i]; }
    for (int i = 1; i < logMaxN; i++) {
        for (int j = 0; j < n; j++) {
            if (sp[i - 1][j] == -1) { sp[i][j] = -1; }
            else { sp[i][j] = sp[i - 1][sp[i - 1][j]]; }
        }
    }
}
int getLCA(int a, int b) {
    if (depth[a] < depth[b]) { swap(a, b); }
    for (int i = logMaxN - 1; i >= 0; i--) {
    assert(a != -1 && b != -1);
        if (sp[i][a] == -1) { continue; }
        if (depth[a] - (1 << i) >= depth[b]) { a = sp[i][a]; }
    }
    assert(depth[a] == depth[b]);
    if (a == b) { return a; }
    for (int i = logMaxN - 1; i >= 0; i--) {
        assert(a != -1 && b != -1);
        if (sp[i][a] != sp[i][b]) {
            a = sp[i][a];
            b = sp[i][b];
        }
    }
    return par[a];
}

vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I) {

    for (auto e : R) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    int n = R.size() + 1, m = D.size();
    par[0] = -1;
    dfs(0);
    initSp(n);
    vector<int> ans;
    for (int i = 0; i < m; i++) {
        int lca = getLCA(S[i], T[i]);
        ans.push_back(I[i] * (depth[S[i]] + depth[T[i]] - 2 * depth[lca] + 1));
    }
    return ans;
}
