#include "infection.h"
#include <vector>
#include <utility>
#include "bits/stdc++.h"

using namespace std;

const int mxn=150020,mxl=20;

int up[mxl][mxn],dp[mxn];
vector<int>aj[mxn];

void dfs(int u, int p, int d) {
    dp[u] = d, up[0][u] = p;
    for (int i = 1; i < mxl; i ++)
        up[i][u] = up[i - 1][up[i - 1][u]];
    for (int v : aj[u]) if (v != p)
        dfs(v, u, d + 1);
}

int lca(int u, int v) {
    if (dp[v] < dp[u]) swap(u, v);
    int d = dp[v] - dp[u];
    for (int i = 0; i < mxl; i ++)
        if (d & 1 << i) v = up[i][v];
    if (u == v) return u;
    for (int i = mxl - 1; i >= 0; i --)
        if (up[i][u] != up[i][v])
            u = up[i][u], v = up[i][v];
    return up[0][u];
}

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
) {
    int m = D.size();
    for (auto eg : R) {
        aj[eg.first].push_back(eg.second);
        aj[eg.second].push_back(eg.first);
    }
    dfs(0, -1, 0);
    vector<int> ans(m);
    for (int i = 0; i < m; i ++) if (I[i])
        ans[i] = dp[S[i]] + dp[T[i]] - 2 * dp[lca(S[i], T[i])] + 1;
    return ans;
}
