#include "infection.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define int long long
using namespace std;
const ll N=50000;
vector <int> v[N+5],anss;
ll fix[N+5],tin[N+5],tout[N+5],up[N+5][40],par[N+5];
ll lg=0,tinn=0,toutt=0;
ll s[N+5];
ll cur[N+5],num[N+5];
ll ans[N+5];
ll alr[N+5];
void dfs(int u,int mom){
	fix[u]=1; par[u]=mom; tinn++; tin[u]=tinn;
/*	for (int i=1; i<=lg; i++){
		up[u][i]=up[up[u][i-1]][i-1];
	}*/
	for (int i=0; i<v[u].size(); i++){
		if (fix[v[u][i]]==1) continue;
		dfs(v[u][i],u);
	}
	toutt++; tout[u]=toutt;
}
bool is_parent(int a,int b){
	if (tin[a]<=tin[b] && tout[a]>=tout[b]) return 1;
	return 0;
}
std::vector<int> solve(
    vector<std::pair<int, int> > R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
) { 
	ll n=R.size()+1;
	ll m=S.size();
	
	
	for (int i=0; i<n; i++) v[i].clear();
	
	for (int i=0; i<n-1; i++){
		v[R[i].f].pb(R[i].s);
		v[R[i].s].pb(R[i].f);
	}
	dfs(0,0); 
	vector <ll> gza[N+5];
	// titoeulis path winaswar vqnat
	for (int i=0; i<m; i++){
		ll x=S[i]; ll y=T[i];
		ll z;
		gza[i].clear();
		while (is_parent(x,y)==0){
		z=par[x]; x=z; gza[i].pb(x); 
		}
		vector <ll> gz;
		gz.clear();
		while (y!=x){
			gz.pb(y); z=par[y]; y=z;
		}
		reverse(gz.begin(),gz.end());
		for (int j=0; j<(int)gz.size(); j++){
			gza[i].pb(gz[j]);
			
		} 
	}
	for (int i=0; i<m; i++){
		cur[i]=S[i]; alr[i]=0;
		if (I[i]==1) s[cur[i]]++,ans[i]=1;
		num[i]=0;
	}
	ll k=0;
	while (1){
		k++;
		
		for (int i=0; i<m; i++){
			if (num[i]>gza[i].size()) continue;
			if (s[cur[i]]>0 && ans[i]==0) {
				ans[i]=1; alr[i]=1; s[cur[i]]++;
			}
			else
			if (alr[i]==1) ans[i]++; // already infected
			if (ans[i]>0) alr[i]=1; 
			
		}//cout<<k<<s[3]<<endl;
		// exa +1 move
		bool ok=0;
		for (int i=0; i<m; i++){
			if (num[i]>=gza[i].size()) {
				num[i]++;
				if (alr[i]==1) s[cur[i]]--;
				continue;
			}
			ok=1;
			if (alr[i]==1) s[cur[i]]--;
			cur[i]=gza[i][num[i]]; num[i]++;
			if (alr[i]==1){
				s[cur[i]]++;
			}
		}
		if (ok==0) break;
		
	}
	
	anss.clear();
	for (int i=0; i<m; i++) anss.pb(ans[i]);
	
    return anss;
}

