#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;

int d[200001];
vector<int> v[200001];
int jump[200001][20];
void dfs(int i,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        d[nb]=d[i]+1;
        jump[nb][0]=i;
        dfs(nb,i);
    }
}

int lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    int j=d[x]-d[y];
    for(int i=0;i<20;i++)
    {
        if((1<<i)&j)
            x=jump[x][i];
    }

    if(x==y)return x;

    for(int i=19;i>=0;i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }
    return jump[x][0];
}

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
)

{
    for(int i=0;i<R.size();i++)
    {
        v[R[i].first].push_back(R[i].second);
        v[R[i].second].push_back(R[i].first);
    }

    dfs(0,-1);
    vector<int> ans;
    for(int i=0;i<D.size();i++)
    {
        int ver=lca(S[i],T[i]);

        int num=d[S[i]]+d[T[i]]-2*d[ver];
        if(I[i]==0)ans.push_back(0);
        else ans.push_back(num+1);
    }
    return ans;
}
