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

using namespace std;

const int nmax = 15e4 + 1;

vector<int> adj[nmax];
int up[nmax][18];
int d[nmax];

void dfs(int i, int tata = 0) {
    for(int j = 1; (1 << j) <= d[i]; j++) {
        up[i][j] = up[up[i][j - 1]][j - 1];
    }
    for(auto it : adj[i]) {
        if(it != tata) {
            d[it] = d[i] + 1;
            up[it][0] = i;
            dfs(it, i);
        }
    }
}

int lift(int a, int n) {
    for(int bit = 0; (1 << bit) <= n; bit++) {
        if((1 << bit) & n) {
            a = up[a][bit];
        }
    }
    return a;
}

int get_lca(int a, int b) {
    if(d[a] > d[b]) {
        swap(a, b);
    }
    b = lift(b, d[b] - d[a]);
    if(a == b) {
        return a;
    }
    for(int bit = 17; bit >= 0; bit--) {
        if(up[a][bit] != up[b][bit]) {
            a = up[a][bit];
            b = up[b][bit];
        }
    }
    return up[a][1];
}

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