#include "infection.h"
#include <vector>
#include <iostream>
#include <utility>
using namespace std;


vector<vector<int>> v;
vector<int> bl[30];
int adan[150001];

void dfs(int nod,int tata){
    bl[0][nod]=tata;adan[nod]=adan[tata]+1;
    for(auto it:v[nod]){
        if(it==tata) continue;
        dfs(it,nod);
    }
}

int lca(int a,int b){
    int i;
    if(adan[a]>adan[b]) swap(a,b);
    for(i=29;i>=0;i--){
        if(adan[bl[i][b]]>=adan[a]) b=bl[i][b];
    }
    for(i=29;i>=0;i--){
        if(bl[i][a]!=bl[i][b]){
            a=bl[i][a];b=bl[i][b];
        }
    }
    return bl[0][a];
}

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()+1,i,j;
    v.resize(n+1);
    for(i=0;i<=n;i++){
        v[i].clear();adan[i]=0;
    }
    for(i=0;i<30;i++){
        bl[i].resize(n+1);
        for(j=0;j<=n;j++) bl[i][j]=0;
    }
    for(i=0;i<n-1;i++){
        v[R[i].first].push_back(R[i].second);
        v[R[i].second].push_back(R[i].first);
    }
    dfs(0,0);
    for(i=1;i<30;i++){
        for(j=0;j<n;j++){
            bl[i][j]=bl[i-1][bl[i-1][j]];
        }
    }
    vector<int> rasp;rasp.clear();
    for(i=0;i<S.size();i++){
        if(I[i]){///printf("a %d %d",S[i],T[i]);
            rasp.push_back(adan[S[i]]+adan[T[i]]-2*adan[lca(S[i],T[i])]+1);///printf("b\n");
        }else rasp.push_back(0);
    }
    return rasp;
}
