#include<bits/stdc++.h>
#include "infection.h"
using namespace std;
using ll=long long;

const ll N=1.5e5+55,inf=1e18;
vector<ll>g[N];
ll up[N][20],tin[N],tout[N],d[N],ti,n,m;

void dfs(ll u,ll p){
    up[u][0]=p;
    tin[u]=++ti;
    for(ll v:g[u]){
        if(!(v^p))continue;
        d[v]=d[u]+1;
        dfs(v,u);
    }
    tout[u]=++ti;
}

bool iznad(ll u,ll v){
    return(tin[u]<=tin[v]&&tout[u]>=tout[v]);
}

ll lca(ll u,ll v){
    if(iznad(u,v))return u;
    if(iznad(v,u))return v;
    for(int j=19;j>=0;--j){
        if(up[u][j]&&!iznad(up[u][j],v))u=up[u][j];
    }
    return up[u][0];
}

ll dist(ll u,ll v){
    return d[u]+d[v]-2*d[lca(u,v)];
}

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
){
    m=S.size();
    n=R.size()+1;

    for(int i=0;i<N;++i){
        g[i].clear();
        for(int j=0;j<20;++j)up[i][j]=0;
        tin[i]=tout[i]=0;
        d[i]=0;
    }
    ti=0;

    for(auto[u,v]:R){
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,0);
    for(int j=1;j<20;++j){
        for(int i=1;i<=n;++i)
            up[i][j]=up[up[i][j-1]][j-1];
    }

    vector<int>ret;
    for(int i=0;i<m;++i){
        if(!I[i])ret.push_back(0);
        else ret.push_back(dist(S[i],T[i]));
    }

    return ret;
}
