#include <bits/stdc++.h>
#include "infection.h"

using namespace std;

const int MAXN = 15e4;
const int MAXLG = 18;

vector<int> tree[1 + MAXN];
int tin[1 + MAXN], tout[1 + MAXN], timer;
int dep[1 + MAXN];

int up[MAXLG][1 + MAXN];

bool is_anc( int u, int v ) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca( int u, int v ) {
  if ( is_anc(u, v) ) return u;
  if ( is_anc(v, u) ) return v;
  for ( int i = MAXLG - 1; i >= 0; --i ) {
    if ( up[i][u] != -1 && !is_anc(up[i][u], v) ) {
      u = up[i][u];
    }
  }
  return up[0][u];
}

int dist( int u, int v ) {
  return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void dfs( int u, int p = -1 ) {
  tin[u] = ++timer;
  for ( auto v : tree[u] ) {
    if ( v == p ) continue;
    up[0][v] = u;
    dep[v] = dep[u] + 1;
    dfs(v, u);
  }
  for ( int i = 1; i < MAXLG; ++i ) {
    up[i][u] = up[i - 1][up[i - 1][u]];
  }
  tout[u] = timer;
}

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, m = D.size();
  for ( auto [u, v] : R ) {
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  for ( int i = 0; i < MAXLG; ++i ) {
    for ( int j = 0; j < n; ++j ) {
      up[i][j] = -1;
    }
  }
  dep[0] = 0;
  dfs(0);
  vector<int> res(m);
  for ( int i = 0; i < m; ++i ) {
    res[i] = (dist(S[i], T[i]) + 1) * I[i];
  }
  timer = 0;
  for ( int i = 0; i < n; ++i ) {
    tree[i].clear();
  }
  return res;
}
