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

const int MAX_N = 150000;
const int LOG_N = 18;

struct Node {
    vector<int> adj;
    int jump[LOG_N + 1];
    int time_in, time_out;
    int depth;
};

Node a[MAX_N];

void read_edges(std::vector<std::pair<int, int>>& R) {
    for (auto [u, v] : R) {
        a[u].adj.push_back(v);
        a[v].adj.push_back(u);
    }
}

void dfs(int node, int parent) {
    static int time = 0;
    a[node].time_in = ++time;
    a[node].depth = parent != -1 ? a[parent].depth + 1 : 0;

    a[node].jump[0] = parent;
    for (int i = 1; i <= LOG_N; i++) {
        if (a[node].jump[i - 1] == -1) a[node].jump[i] = -1;
        else a[node].jump[i] = a[a[node].jump[i - 1]].jump[i - 1];
    }

    // cerr << a[node].depth << ' ';

    for (int child : a[node].adj) {
        if (child == parent) continue;

        dfs(child, node);
    }

    a[node].time_out = ++time;
}

bool is_anc(int u, int v) {
    return a[u].time_in <= a[v].time_in && a[v].time_out <= a[u].time_out;
}

int lca(int u, int v) {
    if (a[u].depth > a[v].depth) swap(u, v);

    if (is_anc(u, v)) return u;

    for (int i = LOG_N; i >= 0; i--) {
        if (a[v].jump[i] == -1) continue;
        if (a[a[v].jump[i]].depth >= a[u].depth) {
            v = a[v].jump[i];
        }
    }

    for (int i = LOG_N; i >= 0; i--) {
        if (a[v].jump[i] == -1 || a[u].jump[i] == -1) continue;

        if (a[v].jump[i] == a[u].jump[i]) continue;

        u = a[u].jump[i];
        v = a[v].jump[i];
    }

    return a[u].jump[0];
}

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
) {
    read_edges(R);
    dfs(0, -1);
    // cerr << "\n\n";

    vector<int> res(D.size());

    for (int i = 0; i < D.size(); i++) {
        if (!I[i]) {
            res[i] = 0;
            continue;
        }

        int l = lca(S[i], T[i]);
        // cerr << "HERE " << a[S[i]].depth << ' ' << a[T[i]].depth << '\n';
        res[i] = a[S[i]].depth + a[T[i]].depth - 2 * a[l].depth + 1;
    }

    return res;
}
