#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
#define int ll
#warning :(( long longul vostru gen e so nenecesar
#define sz(x) ((int)(x).size())
using pii = pair<int, int>;
using tii = tuple<int, int, int>;

const int nmax = 15e4 + 5;

bool isinfected[nmax];
int wheninfected[nmax];
int rez[nmax];


vector<int> g[nmax];
namespace Tree {
	int d[nmax];
	int p[nmax], jump[nmax];
	int pin[nmax], pout[nmax], inp;
	
	void init(int node, int f) {
		d[node] = d[f] + 1;
		p[node] = jump[node] = f;
		if(d[jump[jump[f]]] + d[f] == 2 * d[jump[f]]) jump[node] = jump[jump[f]];
		pin[node] = inp++;
		
		for(auto x : g[node]) {
			if(x == f) continue;
			init(x, node);
		}
		
		pout[node] = inp - 1;
	}
	
	bool isanc(int a, int b) {
		return pin[a] <= pin[b] && pout[b] <= pout[a];
	}
	
	int lca(int a, int b) {
		while(!isanc(a, b)) {
			if(!isanc(jump[a], b)) a = jump[a];
			else a = p[a];
		}
		return a;
	}
	int dist(int a, int b) {
		return d[a] + d[b] - 2 * d[lca(a, b)];
	}
	int kthchain(int a, int k) {
		int target = d[a] - k;
		while(d[a] > target) {
			if(d[jump[a]] > target) a = jump[a];
			else a = p[a];
		}
		return a;
	}
	int kth(int a, int b, int k) {
		int L = lca(a, b), D = d[a] + d[b] - 2 * d[L];
		if(k > D) return -1;
		if(k <= d[a] - d[L]) return kthchain(a, k);
		else return kthchain(b, D - k);
	}
}

std::vector<signed> solve(
	std::vector<std::pair<signed, signed>> R,
	std::vector<long long> D,
	std::vector<signed> S,
	std::vector<signed> T,
	std::vector<bool> I
) {
	int M = sz(D);
	for(auto [a, b] : R) g[a].emplace_back(b), g[b].emplace_back(a);
	Tree::init(1, 1);
	
	priority_queue<pii, vector<pii>, greater<pii>> heap;
	for(int i = 0; i < M; i++) {
		if(I[i]) {
			heap.emplace(D[i], i);
			wheninfected[i] = D[i];
		}
		else
			wheninfected[i] = 1e18 + 5;
	}
	
	while(!heap.empty()) {
		auto [time, node] = heap.top();
		heap.pop();
		if(isinfected[node]) continue;
		isinfected[node] = 1;
		// cerr << node << '\n';
		for(int j = 0; j < M; j++) {
			if(isinfected[j]) continue;
			int a = Tree::kth(S[node], T[node], wheninfected[node] - D[node]), b = T[node], c = wheninfected[node];
			int x = S[j], y = T[j], z = D[j];
			if(c < z)
				a = Tree::kth(a, b, z - c);
			else
				x = Tree::kth(x, y, c - z);
			c = max(c, z);
			if(a == -1 || x == -1) continue;
			// cerr << node << ' ' << j << '\t' << c << '\n';
			do {
				// cerr << a << ' ' << x << '\n';
				if(a == x) { 
					if(wheninfected[j] > c) {
						wheninfected[j] = c;
						heap.emplace(c, j);
					}
					break;
				}
				a = Tree::kth(a, b, 1);
				x = Tree::kth(x, y, 1);
				c++;
			} while(a == -1 || x == -1);
		}
	}
		
	vector<signed> result;
	for(int i = 0; i < M; i++) {
		if(isinfected[i])
			result.emplace_back(Tree::dist(S[i], T[i]) + D[i] - wheninfected[i] + 1);
		else
			result.emplace_back(0);
	}
	return result;
}
#undef int
	
