// #include "infection.h"
#include <vector>
#include <iostream>

//chockolateman

#include<bits/stdc++.h>
#include "infection.h"

using namespace std;

long long N,tin[150005],tout[150005],depth[150005],par[150005],jump[150005],timer,up[150005][20],X[150005],Y[150005];
vector<long long> adj[150005];
vector<int> ans;
vector<pair<long long,long long>> days;
bool status[150005],inf_node[150005];
set<long long> active;
vector<long long> to_remove;

void dfs1(long long v,long long p)
{
    depth[v] = depth[p] + 1;
    tin[v] = ++timer;
    par[v] = p;
    up[v][0] = p;
    for(long long L = 1 ; L <= 17 ; L++)
        up[v][L] = up[up[v][L-1]][L-1];
    for(auto u : adj[v])
        if(u != p)
            dfs1(u,v);
    tout[v] = timer;
}

bool is_ancesstor(long long a,long long b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

long long move(long long a,long long b)
{
    if(!is_ancesstor(a,b))
        return par[a];
    else
    {
        for(long long L = 17 ; L >= 0 ; L--)
            while(!is_ancesstor(up[b][L],a))
                b = up[b][L];
        return b;
    }
}

void update(long long v)
{
    status[v] |= inf_node[X[v]];
    ans[v] += status[v];
    if(X[v] != Y[v])
        X[v] = move(X[v],Y[v]);
    else
        to_remove.push_back(v);
}

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();
    for(long long i = 0 ; i < N ; i++)
    {
        R[i].first++;
        R[i].second++;
        adj[R[i].first].push_back(R[i].second);
        adj[R[i].second].push_back(R[i].first);
    }
    dfs1(1,1);
    long long M = D.size();
    for(long long i = 0 ; i < M ; i++)
    {
        X[i] = S[i]+1;
        Y[i] = T[i]+1;
        days.push_back({D[i],i});
        status[i] = I[i];
    }
    sort(days.begin(),days.end());
     long long pos = 0;
    long long t = 0;
    ans.assign(M,0);
    while(!active.empty() || pos < M)
    {
        while(pos < M && days[pos].first <= t)
        {
            active.insert(days[pos].second);
            pos++;
        }
        if(!active.empty())
        {
            for(long long i = 1 ; i <= N ; i++)
               inf_node[i] = false;
            for(auto v : active)
                inf_node[X[v]] |= status[v];
            for(auto v : active)
                update(v);
            for(auto v : to_remove)
                active.erase(v);
            to_remove.clear();
        }
        // else
        //     t = days[pos].first;
        t++;
    }
    return ans;
}