#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,cnt,tin[N],tout[N],p[N][20],dp[N];
vector <int> v[N];
void dfs(int i,int pr){
	tin[i]=++cnt; p[i][0]=pr;
	dp[i]=dp[pr]+1;
	for (int j=1; j<20; j++)
		p[i][j]=p[p[i][j-1]][j-1];
	for (int j:v[i]){
		if (j==pr) continue;
		dfs(j,i);
	} tout[i]=cnt;
}
bool isp(int a,int b){
	return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int a,int b){
	if (isp(a,b)) return a;
	if (isp(b,a)) return b;
	for (int j=19; j>=0; j--)
		if (p[a][j]!=0 && !isp(p[a][j],b)) a=p[a][j];
	return p[a][0];
}
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I) {
	n=(int)R.size()+1,m=(int)D.size();
    vector <int> va(m,0);
    for (int i=0; i<=n; i++) v[i].clear();
    for (int i=0; i<n-1; i++){
    	R[i].first++; R[i].second++;
    	v[R[i].first].push_back(R[i].second);
    	v[R[i].second].push_back(R[i].first);	
	} vector <pair<int,int>> vd;
	vector <int> dt(m,0);
	cnt=0; dp[0]=0; dfs(1,0);
	for (int i=0; i<m; i++){
		S[i]++,T[i]++;
		vd.push_back({D[i],i});
		dt[i]=dp[S[i]]+dp[T[i]]-2*dp[lca(S[i],T[i])];
	} sort(vd.begin(),vd.end()); int id=0,x=0;
	vector <int> vp(m,0);
//	for (int i=0; i<(int)vd.size(); i++) cout<<vd[i].first<<" "<<vd[i].second<<endl;
	while (id<(int)vd.size()){
		for (int i=0; i<m; i++){
			if (vp[i]==0) continue;
			if (vp[i]==T[i]) vp[i]=0;
			else if (isp(vp[i],T[i])){
				for (int j:v[vp[i]]){
					if (j==p[vp[i]][0]) continue;
					if (isp(j,T[i])){
						vp[i]=j; break;
					}
				}
			}
			else vp[i]=p[vp[i]][0];
		//	if (i==0) cout<<vp[i]<<"!"<<endl;
		}
		while (id<(int)vd.size() && vd[id].first<=x){
			vp[vd[id].second]=S[vd[id].second]; id++;
		} bool bl=0;
		for (int i=0; i<m; i++)
			if (vp[i]!=0) bl=1;
		if (!bl){
			if (id<(int)vd.size()) x=vd[id].first; continue;
		} vector <bool> bb(n+1,0);
		for (int i=0; i<m; i++){
			if (vp[i]!=0 && I[i]) bb[vp[i]]=1;
		}
		for (int i=0; i<m; i++){
			if (bb[vp[i]]) I[i]=1;
			if (I[i] && vp[i]!=0){
				va[i]++;// cout<<i<<" "<<x<<" "<<vp[i]<<endl;
			}
		} x++;
	}  return va;
}
