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

vector<vector<int>> adj;
vector<int> tin;
vector<int> tout;
vector<vector<int>> up;
vector<int> dept;
int l;
int timer=-1;

void dfs(int u, int p){
    timer++;
    tin[u]=timer;
    up[u][0]=p;
    for(int i=1;i<=l;i++)up[u][i]=up[up[u][i-1]][i-1];
    for(int v:adj[u]){
        if(v!=p){
            dept[v]=dept[u]+1;
            dfs(v,u);
        }
    }
    timer++;
    tout[u]=timer;
}

bool isanc(int u, int v){
    if(tin[u]<=tin[v] and tout[u]>=tout[v])return true;
    else return false;
}

int lca(int u, int v){
    if(isanc(u,v))return u;
    if(isanc(v,u))return v;
    for(int i=l;i>=0;i--){
        if(!isanc(up[u][i],v))u=up[u][i];
    }
    return up[u][0];
}

vector<int> gt;
void fp(int u, int p, int t){
    if(u==t){
        gt[u]=0;
        return;
    }
    for(auto v:adj[u]){
        if(v!=p){
            fp(v,u,t);
            if(gt[v]!=-1){
                gt[u]=v;
                return;
            }
        }
    }
}

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
) {
    int m=S.size();
    int n=R.size()+1;
    adj.resize(n);
    dept.resize(n);
    tin.resize(n);
    tout.resize(n);
    gt.resize(n);
    l=ceil(log2(n));
    up.resize(n,vector<int>(l+1));
    for(auto [u,v]:R){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0,0);
    vector<pair<ll,pair<int,int>>> mv;
    vector<ll> ed(m);
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        int rt=lca(S[i],T[i]);
        int bg=S[i]+T[i]-2*dept[rt]+1;
        if(I[i]==1)ans[i]=bg;
    }
    return ans;
}