#include "infection.h"
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <set>
using namespace std;

vector<vector<int>> g, bin_pow;
vector<int> tin, tout, h;

int t = 0;

void dfs(long long v, long long p) {
    tin[v] = t;
    t++;
    bin_pow[0][v] = p;
    for (long long i = 1; i < 20; i++) {
        bin_pow[i][v] = bin_pow[i - 1][bin_pow[i - 1][v]];
    }
    for (auto &i : g[v]) {
        if (i == p) {
            continue;
        }
        h[i] = h[v] + 1;
        dfs(i, v);
    }
    tout[v] = t;
    t++;
}

bool is_p(long long a, long long b) {//is a parent of b
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

long long lca(long long a, long long b) {
    if (is_p(a, b)) {
        return a;
    }
    if (is_p(b, a)) {
        return b;
    }
    for (long long i = 19; i >= 0; i--) {
        if (!is_p(bin_pow[i][a], b)) {
            a = bin_pow[i][a];
        }
    }
    return bin_pow[0][a];
}

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
) {
    long long n = R.size() + 1;
    long long m = D.size();
    g.resize(n);
    tin.resize(n);
    tout.resize(n);
    h.resize(n);
    bin_pow.resize(20, vector<int> (n));
    for (auto &[u, v] : R) {
        // cout << u << " " << v << endl;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0, 0);
    vector<int> ans(m);
    for (long long i = 0; i < m; i++) {
        if (!I[i]) {
            continue;
        }
        long long u = S[i], v = T[i];
        ans[i] = h[u] + h[v] - 2 * h[lca(u, v)] + 1;
    }


    return ans;
}