#include "infection.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <queue>
using namespace std;
#define ll long long
const int N = 3e5 + 1;
vector<int> g[N];
bool vis[N];
int p[N];
int dep[N];
int up[N][21];
void dfs(int v, int x) {
    p[v] = x;
    dep[v] = 0;
    up[v][0] = x;
    dep[v] = dep[x] + 1;
    for (int i = 1; i < 21;++i) {
        if (up[v][i - 1] == -1) {
            continue;
        }
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (auto i : g[v]) {
        if (i != x) {
            dfs(i, v);
        }
    }
}
int ret(int v,int x){
    if (x == 0) {
        return v;
    }
    int o = log2(x);
    x -= (1 << o);
    return ret(up[v][o],x);
}
int lca(int u, int v) {
    if (u == v) {
        return u;
    }
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    if (dep[v] > dep[u]) {
        return lca(u, ret(v, dep[v] - dep[u]));
    }
    for (int i = 20; i >= 0; --i) {
        if (up[v][i] != up[u][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][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
) {
    int n = r.size() + 1;
    int m = d.size();
    vector<queue<int>> nxt(m);
    vector<int> answ(m, 0);
    vector<int> varak(n + 1, 0);
    for (auto i : r) {
        g[i.first].push_back(i.second);
        g[i.second].push_back(i.first);
    }
    dfs(0, -1);
    for (int i = 0; i < m; ++i) {
        if (I[i]) {
            int h = lca(s[i], t[i]);
            answ[i] = dep[s[i]]+dep[t[i]] - 2 * dep[h]+1;
        }
    }
    return answ;
}