#include "infection.h"
#include <vector>
#include <bits/stdc++.h>
#include <utility>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 10;
int dep[maxn];
vector < int > g[maxn];

int n, m, p[maxn];
void dfs(int beg, int from, int h)
{
    dep[beg] = h;
    p[beg] = from;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        dfs(nb, beg, h +1);
    }
}
int jump[maxn][22];

int moveup(int ver, int x)
{
    for (int i = 0; i < 22; ++ i)
        if(x & (1 << i))ver = jump[ver][i];
    return ver;
}
int lca(int u, int v)
{
    int depu = dep[u], depv = dep[v];
    int delta = abs(depu - depv);
    if(depu > depv)
        u = moveup(u, delta);
    else v = moveup(v, delta);
    for (int i = 21; i >= 0; -- i)
    {
        int du = moveup(u, (1 << i));
        int dv = moveup(v, (1 << i));
        if(dv == du)continue;
        u = du;
        v = dv;
    }
    return p[u];
}
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;
    m = D.size();
    for (auto &[from, to]: R)
    {
        g[from].pb(to);
        g[to].pb(from);
    }
    dfs(0, -1, 0);
    for (int i = 0; i < n; ++ i)
        jump[i][0] = p[i];
    for (int j = 0; j < 22; ++ j)
    {
        for (int i = 0; i < n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
    }

    vector < int > ans;

    for (int i = 0 ; i < m; ++ i)
    {
        int s = S[i];
        int t = T[i];
        int meet = lca(s, t);
        int dist = dep[s] + dep[t] - 2*dep[meet] + 1;
        if(I[i])ans.pb(dist);
        else ans.pb(0);
    }
    return ans;
}
