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

#define pb push_back
using ll = long long;
#define int ll
using pi = array<int, 2>;
using ti = array<int, 3>;

const int H = 20;

vector<int32_t> solve(vector<pair<int32_t, int32_t>> R, vector<long long> D, vector<int32_t> S, vector<int32_t> T, vector<bool> I) {
  int n = R.size() + 1, m = D.size();
  
  vector<vector<int>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    adj[R[i].first].pb(R[i].second);
    adj[R[i].second].pb(R[i].first);
  }
  
  vector<int> dep(n);
  vector<vector<int>> jmp(H, vector<int>(n));
  auto dfs = [&](auto &&self, int u) -> void {
    for (int h = 1; h < H; ++h) {
      jmp[h][u] = jmp[h - 1][jmp[h - 1][u]];
    }
    for (int v : adj[u]) {
      if (v == jmp[0][u]) continue;
      dep[v] = dep[u] + 1;
      jmp[0][v] = u;
      self(self, v);
    }
  };
  dfs(dfs, 0);
  
  auto lca = [&](int u, int v) -> int {
    if (dep[u] < dep[v]) swap(u, v);
    
    for (int h = H - 1; h >= 0; --h) {
      if ((dep[u] - dep[v]) & (1 << h)) {
        u = jmp[h][u];
      }
    }
    if (u == v) {
      return u;
    }
    for (int h = H - 1; h >= 0; --h) {
      if (jmp[h][u] != jmp[h][v]) {
        u = jmp[h][u];
        v = jmp[h][v];
      }
    }
    return jmp[0][u];
  };
  
  vector<int32_t> ans(m);
  for (int i = 0; i < m; ++i) {
    if (I[i] == 0) continue;
    int u = lca(S[i], T[i]);
    ans[i] = dep[S[i]] + dep[T[i]] - 2 * dep[u] + 1;
  }
  return ans;
}
