#include "infection.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=150050,lg=18;
vector<int>E[N];
int par[N][lg+1],depth[N];
void DFS(int u,int p=0){
    par[u][0]=p;
    depth[u]=depth[p]+1;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u])if(i!=p)DFS(i,u);
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
map<ll,vector<pair<int,int>>>mapa;
vector<int>solve(vector<pair<int,int>>R,vector<long long>D,vector<int>S,vector<int>T,vector<bool>I){
    int n=R.size()+1;
    for(auto &[u,v]:R)u++,v++;
    for(auto &i:S)i++;
    for(auto &i:T)i++;
    for(auto [u,v]:R){
        E[u].pb(v);
        E[v].pb(u);
    }
    DFS(1);
    int q=S.size();
    vector<int>res(q);
    bool was[n+5]={0};
    bool active[q+5]={0};
    for(int i=0;i<q;i++){
        int u=S[i],v=T[i],t=D[i];active[i]=I[i];
        int c=LCA(u,v);
        vector<int>vtx;
        while(u!=c)vtx.pb(u),u=par[u][0];
        vtx.pb(c);
        vector<int>temp;
        while(v!=c)temp.pb(v),v=par[v][0];
        reverse(temp.begin(),temp.end());
        for(auto i:temp)vtx.pb(i);
        for(int j=0;j<vtx.size();j++){
            mapa[t+j].pb({vtx[j],i});
        }
    }
    for(auto [vreme,vtx]:mapa){
        for(auto [u,i]:vtx)if(active[i])was[u]=true;
        for(auto [u,i]:vtx)if(was[u])active[i]=true;
        for(auto [u,i]:vtx)if(active[i])res[i]++;
        for(auto [u,i]:vtx)was[u]=false;
    }
    return res;
}
