#include "infection.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define speedup cin.tie(0) -> sync_with_stdio(0)
#define all(x) begin(x), end(x)
#define pb push_back
#define vc vector

using ll = long long;
using pii = pair<int, int>;
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}

const int LG = 25;
vc<int> solve( vc<pii> ed, vc<ll> dst, vc<int> st, vc<int> ft, vc<bool> bad) {
	int n = ed.size() + 1;
	int m = st.size();
	vc<vc<int>> adj (n);
	for (auto [u, v] : ed) {
		adj[u].pb(v);
		adj[v].pb(u);	
	}
	
	int cnt = 0;
	vc<array<int, LG>> up (n);
	vc<int> in (n), out (n), d (n);
	auto dfs = [&](auto &&dfs, int u, int p) -> void {
		in[u] = cnt++;
		up[u][0] = p;
		d[u] = d[p] + 1;
		for (int k = 1; k < LG; k++)
			up[u][k] = up[up[u][k - 1]][k - 1];
		
		for (int v : adj[u]) if (v != p) dfs(dfs, v, u);
		out[u] = cnt++;
	}; dfs(dfs, 0, 0);
	auto is = [&](int u, int v) -> bool {return in[u] <= in[v] && out[v] <= out[u];};
	auto lca = [&](int u, int v) -> int {
		if (is(u, v) || is(v, u)) return is(u, v) ? u : v;
		for (int k = LG - 1; k >= 0; k--) if (!is(up[u][k], v)) u = up[u][k];
		
		return up[u][0];
	};
	
	vc<int> ans (m);
	for (int i = 0; i < m; i++) {
		if (bad[i]) {
			int u = st[i], v = ft[i], p = lca(u, v);
			ans[i] = d[u] + d[v] - 2 * d[p] + 1;
		}
	}
	
	return ans;
}