#include <bits/stdc++.h>
#include "infection.h"
using namespace std;
vector<int>d;
vector<vector<int>>g;
vector<vector<int>>lca;
void dfs(int a,int b)
{
    lca[a][0]=b;
    d[a]=d[b]+1;
    for(int i=1;i<20;i++)
    {
        lca[a][i]=lca[lca[a][i-1]][i-1];
    }
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfs(i,a);
        }
    }
}
int findlca(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int i=19;i>=0;i--)
    {
        if(d[lca[a][i]]>=d[b])a=lca[a][i];
    }
    if(a==b)return a;
    for(int i=19;i>=0;i--)
    {
        if(lca[a][i]!=lca[b][i])
        {
            a=lca[a][i];
            b=lca[b][i];
        }
    }
    return lca[a][0];
}
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I)
{
    int n=R.size(),m=S.size();
    vector<int>res;
    d.resize(n+1);
    g.resize(n+1);
    lca.resize(n+1,vector<int>(20));
    for(int i=0;i<n;i++)
    {
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }
    dfs(0,0);
    for(int i=0;i<m;i++)
    {
        if(I[i]==0)res.push_back(0);
        else
        {
            int c=findlca(S[i],T[i]);
            res.push_back(d[S[i]]+d[T[i]]-2*d[c]+1);
        }
    }
    return res;
}
