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

using namespace std;

const int maxn = 150005;
const int MAXLOG = 18;

int n, q;
vector<int> g[maxn];
int depth[maxn];
int jump[maxn][MAXLOG];

void dfs(int node, int par, int d)
{
    depth[node] = d;
    jump[node][0] = par;
    for (auto to : g[node])
    {
        if (to != par)
        {
            dfs(to, node, d + 1);
        }
    }
}

int findLCA(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    int diff = depth[x] - depth[y];

    for (int i = 0; i < MAXLOG; ++i)
    {
        if ((diff & (1 << i)) != 0)
        {
            x = jump[x][i];
            diff ^= (1 << i);
            if (diff == 0) break;
        }
    }

    if (x == y) return x;

    for (int i = MAXLOG - 1; i >= 0; --i)
    {
        if (jump[x][i] != jump[y][i])
        {
            x = jump[x][i];
            y = jump[y][i];
        }
    }

    return jump[x][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
) {
    n = R.size() + 1;

    for (auto [x, y] : R)
    {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(0, 0, 1);

    for (int i = 1; i < MAXLOG; ++i)
    {
        for (int node = 0; node < n; ++node)
        {
            jump[node][i] = jump[jump[node][i - 1]][i - 1];
        }
    }

    vector<int> ans;

    for (int i = 0; i < D.size(); ++i)
    {
        int from = S[i], to = T[i];
        ans.push_back(depth[from] + depth[to] - 2 * depth[findLCA(from, to)] + 1);
    }

    return ans;
}
