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

const int MAX = 2E5 , LOG = 19;
int up[MAX][LOG];

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 N = (int)R.size() + 1;

   vector<vector<int>> g(N + 1);
   for(auto [u , v] : R){
      u++;
      v++;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
   }

   vector<int> d(N + 1);
   function<void(int , int)> dfs = [&](int u , int P){
      d[u] = d[P] + 1;
      up[u][0] = P;
      for(int v : g[u]){
         if(v != P){
            dfs(v , u);
         }
      }
   };
   dfs(1 , 1);
   for(int b = 1;b < LOG;b ++){
      for(int i = 1;i <= N;i ++){
         up[i][b] = up[up[i][b - 1]][b - 1];
      }
   }

   auto lca = [&](int u , int v){
      if(d[u] < d[v]){
         swap(u , v);
      }
      for(int b = 0;b < LOG;b ++){
         if((d[u] - d[v]) >> b & 1){
            u = up[u][b];
         }
      }
      if(u == v){
         return u;
      }
      for(int b = LOG - 1;b >= 0;b --){
         if(up[u][b] != up[v][b]){
            u = up[u][b];
            v = up[v][b];
         }
      }
      return up[u][0];
   };

   auto dist = [&](int u , int v){
      return d[u] + d[v] - 2 * d[lca(u , v)];
   };

   vector<int> ans((int)D.size());
   for(int i = 0;i < (int)D.size();i ++){
      if(I[i]){
         ans[i] = dist(S[i] + 1 , T[i] + 1);
      }
   }
    return ans;
}