#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second

const int mxN = 2e5 + 5;
ll n,d[mxN],m,s[mxN],t[mxN],dis[mxN],tam[mxN],p[mxN][20],in[mxN],out[mxN],tt;
bool val[mxN];
ll ans[mxN];
vector<int> v[mxN];

void dfs(ll at, ll par){
	in[at] = tt++;
	for(int i = 1; i < 20; i++) p[at][i] = p[p[at][i - 1]][i - 1];
	for(auto it : v[at]){
		if(it == par) continue;
		dis[it] = dis[at] + 1;
		p[it][0] = at;
		dfs(it, at);
	}
	out[at] = tt;
}

bool check(ll a, ll b){
	return (in[a] <= in[b] and out[a] >= out[b]);
}

ll lca(ll a, ll b){
	if(check(a, b)) return a;
	for(int i = 19; i >= 0; i--){
		if(!check(p[a][i], b)) a = p[a][i];
	}
	return p[a][0];
}

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
){
    n = R.size() + 1;
    m = D.size();
    for(auto it : R){
    	v[it.ff].pb(it.sd);
    	v[it.sd].pb(it.ff);
	}
	for(int i = 0; i < m; i++) ans[i] = 1e13;
	p[1][0] = 1;
	dfs(1, 1);
	for(int i = 0; i < m; i++){
		d[i] = D[i];
		s[i] = S[i];
		t[i] = T[i];
		val[i] = I[i];
		if(val[i]) ans[i] = D[i];
		tam[i] = 2 * dis[lca(t[i], s[i])] + dis[t[i]] + dis[s[i]] + d[i];
	}
	vector<int> res;
	for(int i = 0; i < m; i++){
		res.pb(max(0LL, tam[i] - ans[i] + 1));
	}
	return res;
}
