#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iterator>
#include <cassert>
#include <queue>
#include "infection.h"
using namespace std;

#define dbg(x) cerr << #x << ' '; print(x); cerr << endl;
void print(int x) { cerr << x; }
void print(long long x) { cerr << x; }
void print(char x) { cerr << x; }
void print(string x) { cerr << x; }
void print(double x) { cerr << x; }
template <class T> void print(vector <T> x);
template <class T> void print(vector <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T> void print(set <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T> void print(multiset <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T, class V> void print(pair <T, V> x) { cerr << "{"; print(x.first); cerr << ' '; print(x.second); cerr << "}"; }

#define ll long long
#define OK cerr << "OK\n"
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define PII pair <int, int>
#define MP make_pair
#define inf 1e9 + 5
#define inf64 1e18 + 5;
#define pb push_back

const int N = 150005, LOG = 21;
int n, m, p[N], dist[N], up[N][LOG];
vector <int> G[N], answ;

void dfs(int node, int parent) {
	dist[node] = dist[parent] + 1;
	up[node][0] = parent;
	for (int u : G[node]) {
		if (u == parent) continue;
		dfs(u, node);
	}
}

int lca(int a, int b) {
	if (dist[a] < dist[b]) swap(a, b);
	for (int j = LOG - 1; j >= 0; j--) {
		if (up[a][j] != -1 && dist[up[a][j]] >= dist[b]) a = up[a][j];
	}
	if (a == b) return a;
	for (int j = LOG - 1; j >= 0; j--) {
		if (up[a][j] != up[b][j]) {
			a = up[a][j];
			b = up[b][j];
		}
	}
	return up[a][0];
}

vector<int> solve(
	vector<std::pair<int, int>> R,
	vector<long long> D,
	vector<int> S,
	vector<int> T,
	vector<bool> I
) {
	n = R.size() + 1;
	m = D.size();
	for (int i = 0; i < n - 1; i++) {
		G[R[i].first].pb(R[i].second);
		G[R[i].second].pb(R[i].first);
	}
	dfs(0, -1);
	for (int j = 1; j < LOG; j++) {
		for (int i = 0; i < n; i++) {
			if (up[i][j - 1] == -1) {
				up[i][j] = -1;
				continue;
			}
			up[i][j] = up[up[i][j - 1]][j - 1];
		}
	}
	answ.resize(m, -1);
	for (int i = 0; i < m; i++) {
		answ[i] = dist[S[i]] + dist[T[i]] + 1 - 2 * dist[lca(S[i], T[i])];
		answ[i] *= I[i];
	}
	return answ;
}
