#include "infection.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5+5;
const int LOG = 20;
const int inf = 1e18;


int n, m;
vector<int> g[MAXN];
int d[MAXN];
int up[MAXN][LOG];

void dfs(int x, int p){
    for(int i = 1; i < LOG; ++i){
        up[x][i] = up[up[x][i-1]][i-1];
    }
    for(int k : g[x]){
        if(k==p) continue;
        up[k][0] = x;
        d[k] = d[x]+1;
        dfs(k,x);
    }
}

int lift(int x, int k){
    for(int i = LOG-1; i >= 0; --i){
        if((1<<i) <= k){
            x = up[x][i];
            k -= (1<<i);
        }
    }
    return x;
}
int lca(int x, int y){
    if(d[x] < d[y]) swap(x,y);
    x = lift(x,d[x]-d[y]);
    if(x == y) return x;
    for(int i = LOG-1; i >= 0; --i){
        if(up[x][i] != up[y][i]){
            x = up[x][i], y = up[y][i];
        }
    }
    return up[x][0];
}
int dist(int x, int y){
    int z = lca(x, y);
    return d[x] + d[y] - 2*d[z];
}

std::vector<int32_t> solve(
    std::vector<std::pair<int32_t, int32_t>> R,
    std::vector<long long> D,
    std::vector<int32_t> S,
    std::vector<int32_t> T,
    std::vector<bool> I
){
    n = R.size()+1;
    m = D.size();
    for(auto [x,y] : R){
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0,0);
    vector<int32_t> ans(m,0);
    for(int i = 0; i < m; ++i){
        if(I[i]) ans[i] = dist(S[i], T[i]) + 1;
    }
    return ans;
}
