//chockolateman

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

using namespace std;

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

void dfs1(int v,int p)
{
    depth[v] = depth[p] + 1;
    tin[v] = ++timer;
    par[v] = p;
    up[v][0] = p;
    for(int 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(int a,int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int LCA(int a,int b)
{
    if(is_ancesstor(a,b))
        return a;
    for(int L = 17 ; L >= 0 ; L--)
        if(!is_ancesstor(up[a][L],b))
            a = up[a][L];
    a = up[a][0];
    return a;
}

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

void update(int 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);
}

int dist(int a,int b)
{
    int lca = LCA(a,b);
    return depth[a] - depth[lca] + depth[b] - depth[lca];
}

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(int 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);
    }
    jump[1] = 1;
    dfs1(1,1);
    int M = D.size();
    for(int i = 0 ; i < M ; i++)
    {
        X[i] = S[i]+1;
        Y[i] = T[i]+1;
        inf_node[X[i]] |= I[i];
        status[i] = I[i];
    }
    ans.assign(M,0);
    for(int i = 0 ; i < M ; i++)
        if(inf_node[X[i]])
            ans[i] = X[i] - Y[i] + status[i];
        else
            ans[i] = 0;
    return ans;
}