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

const int MAX = (2e5)+5;

int p[MAX],d[MAX],sp[MAX][20];
int n;
vector<int>v[MAX];

void Dfs(int g,int par)
{
    p[g] = par;
    d[g] = d[par]+1;
    for(int i =0;i<v[g].size();i++)
    {
        if(v[g][i]!=par)
            Dfs(v[g][i],g);
    }
}

void SpTable()
{

    for(int i=1; i<=n; i++)
        sp[i][0] = p[i];
    for(int j=1; j<20; j++)
    {
        for(int i=1; i<=n; i++)
            sp[i][j] = sp[sp[i][j-1]][j-1];
    }
}

pair<int,int> Level(int s,int t)
{
    if(d[s]>d[t])
        swap(s,t);
    pair<int,int>op;
    op.first = s;
    op.second = t;
    for(int i = 19; i>=0; i--)
    {
        if(d[sp[op.second][i]] >= d[op.first])
            op.second = sp[op.second][i];
    }
    return op;
}

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

vector<int> solve(vector<pair<int, int>> r,vector<long long> D,vector<int> s,vector<int> t,vector<bool> inf)
{
    for(int i = 0; i<r.size(); i++)
    {
        r[i].first++;
        r[i].second++;
        v[r[i].first].push_back(r[i].second);
        v[r[i].second].push_back(r[i].first);
    }
    n=r.size()+1;
    Dfs(1,0);
    SpTable();
    vector<int>ans(D.size());
    pair<int,int>op;
    for(int i = 0; i<D.size(); i++)
    {
        s[i]++;
        t[i]++;
        if(inf[i] == 0)
            ans[i] = 0;
        else
        {
            op = Level(s[i],t[i]);
            int lca = Lca(op.first, op.second);
            //cout<<op.first<<" "<<op.second<<" "<<lca<<endl;
            ans[i] = d[s[i]] + d[t[i]] - 2*d[lca] + 1;
        }
    }
    return ans;
}

