#include "bits/stdc++.h"
#include "infection.h"
// #include "grader.cpp"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int N = 2e5+5;
const int LOG = 20;
vector<int> adj[N];
int d[N], sp[N][LOG];

int get(int x, int k){
    for(int i = LOG-1; i >= 0; --i)
        if(k>>i&1)
            x=sp[x][i];
    return x;
}

int lca(int a, int b){
    if(d[a]>d[b])
        swap(a, b);
    b=get(b, d[a]-d[b]);
    if(a==b)
        return a;
    for(int i = LOG-1; i >= 0; --i)
        if(sp[a][i]!=sp[b][i])
            a=sp[a][i], b=sp[b][i];
    return sp[a][0];
}

int dis(int a, int b){
    a++, b++;
    return d[a]+d[b]-2*d[lca(a, b)];
}

void dfs(int x, int pr){
    sp[x][0]=pr;
    for(auto i : adj[x])
        if(i!=pr){
            d[i]=d[x]+1;
            dfs(i, x);
        }
}

vector<int> solve(vector<pii> R, vector<ll> D, vector<int> S, vector<int> T, vector<bool> I){
    int n=(int)R.size()+1;
    for(int i = 0; i < n-1; ++i){
        adj[R[i].ff+1].pb(R[i].ss+1);
        adj[R[i].ss+1].pb(R[i].ff+1);
    }
    dfs(1, 0);
    for(int j = 1; j < LOG; ++j)
        for(int i = 1; i <= n; ++i)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    int m=(int)D.size();
    vector<int> ans(m, 0);
    int down=1e6;
    for(int ad = 0; ad < m; ++ad){
        if(I[ad]==0)
            continue;
        assert(D[ad]==(down*1ll*ad));
        ans[ad]=dis(S[ad], T[ad]);
    }
    return ans;
}