#include <bits/stdc++.h>
#include "infection.h"
const int MAXN = 150'000;
const int MAXLOG = 18;
std::vector<int> adj[MAXN + 1];
int p[MAXN + 1];
int h[MAXN + 1];
struct LCA{
  int rmq[MAXLOG + 1][2 * MAXN + 1];
  int tin[MAXN + 1], tout[MAXN + 1];
  int time = 0;
  int e[2 * MAXN + 1];
  void dfs(int node, int par, int height) {
    p[node] = par;
    h[node] = height;
    rmq[0][++time] = node;
    tin[node] = time;
    for( int x : adj[node] ) {
      if(x != par) {
        dfs(x, node, height + 1);
        rmq[0][++time] = node;
      }
    }
    tout[node] = time;
  }
  void build() {
    dfs(0, -1, 0);
    for( int i = 2; i <= time; i++ ) {
      e[i] = e[i / 2] + 1;
    }
    for( int lg = 1; lg <= MAXLOG; lg++ ) {
      for( int i = 1; i <= time - (1 << lg) + 1; i++ ) {
        rmq[lg][i] = (h[rmq[lg - 1][i]] < h[rmq[lg - 1][i + (1 << (lg - 1))]] ?
                      rmq[lg - 1][i] : rmq[lg - 1][i + (1 << (lg - 1))]);
      }
    }
  }
  int query(int a, int b) {
    int a1 = tin[a];
    int b1 = tin[b];
    if(a1 > b1)
      std::swap(a1, b1);
    int lg = e[b1 - a1 + 1];
    return (h[rmq[lg][a1]] < h[rmq[lg][b1 - (1 << lg) + 1]] ?
            rmq[lg][a1] : rmq[lg][b1 - (1 << lg) + 1]);
  }
}lca;

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 = R.size() + 1;
  for( int i = 0; i < n - 1; i ++ ) {
    adj[R[i].first].push_back(R[i].second);
    adj[R[i].second].push_back(R[i].first);
  }
  lca.build();
  int m = I.size();
  std::vector<int> ans(m);
  for( int i = 0; i < m; i++ ) {
    if(I[i]){
      ans[i] = h[S[i]] + h[T[i]] - 2 * h[lca.query(S[i], T[i])] + 1;
    }else{
      ans[i] = 0;
    }
  }
  return ans;
}
