#include <bits/stdc++.h>
#include "infection.h"

using namespace std;

typedef long long ll;

const int maxn=150005;
const int logmaxn=20;
int n,m;
vector<int>v[maxn];
int depth[maxn];
int in[maxn],out[maxn];
int anc[maxn][logmaxn];

int t=0;
void dfs(int node,int parent)
{
    in[node]=t++;
    depth[node]=depth[parent]+1;
    anc[node][0]=parent;

    for(int i : v[node])
    {
        if(i==parent)
            continue;
        dfs(i,node);
    }

    out[node]=t++;
}

void precomp()
{
    for(int j=1;j<logmaxn;j++)
    {
        for(int i=1;i<n;i++)
        {
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
        }
    }
}

bool is_ancestor(int a,int b)
{
    return (in[a]<in[b] && out[b]<out[a]);
}

int query(int a,int b)
{
    if(is_ancestor(a,b))
        return a;
    if(is_ancestor(b,a))
        return b;

    for(int j=logmaxn-1;j>=0;j--)
    {
        if(anc[b][j]!=-1 && !is_ancestor(anc[b][j],a))
            b=anc[b][j];
    }

    return anc[b][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)
{
    n=R.size()+1;
    m=D.size();

    for(pair<int,int> i : R)
    {
        v[i.first].push_back(i.second);
        v[i.second].push_back(i.first);
    }

    memset(anc,-1,sizeof(anc));
    dfs(0,-1);

    precomp();

    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<logmaxn;j++)
            cout<<anc[i][j]<<' ';
        cout<<endl;
    }*/

    vector<int>ret;
    for(int i=0;i<m;i++)
    {
        if(I[i]==0)
            ret.push_back(0);
        else
        {
            int lca=query(S[i],T[i]);
            //cout<<S[i]<<' '<<T[i]<<' '<<lca<<endl;
            int currans=depth[S[i]]+depth[T[i]]-2*depth[lca]+1;

            ret.push_back(currans);
        }
    }

    return ret;
}
