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

#define ll long long
const ll N=150001;
const ll INF=1e18;
const ll LOG=20;
vector<int>G[N];

ll up[LOG][N];
ll dep[N];

void dfs(int v,int p){
      dep[v]=dep[p]+1;
      if(v>0){
            up[0][v]=p;
            for(int i=1;i<LOG;i++) up[i][v]=up[i-1][up[i-1][v]];
      }
      for(int u:G[v]) if(u!=p) dfs(u,v);
}

int LCA(int a,int b){
      if(dep[a]<dep[b]) swap(a,b);
      int dif=dep[a]-dep[b];
      for(int i=0;i<LOG;i++){
            if((1ll<<i)&dif) a=up[i][a];
      }
      if(a==b) return a;
      for(int i=LOG-1;i>=0;i--){
            if(up[i][a]!=up[i][b]){
                  a=up[i][a];
                  b=up[i][b];
            }
      }
      return up[0][a];
}

ll dd(int a,int b){
      int lca=LCA(a,b);
      return (dep[a]-dep[lca])+(dep[b]-dep[lca]);
}

vector<int>solve(vector<pair<int, int>>R,vector<long long>D,vector<int>S,vector<int>T,vector<bool>I)
{
      int n=(int)R.size()+1;
      for(int i=0;i<n-1;i++){
            G[R[i].first].push_back(R[i].second);
            G[R[i].second].push_back(R[i].first);
      }
      dfs(0,-1);
      int m=(int)S.size();
      vector<int>ans(m,0);
      for(int i=0;i<m;i++){
            if(!I[i]) continue;
            ans[i]=dd(S[i],T[i])+1;
      }
      return ans;
}
