#include "infection.h"
#include <vector>
#include <utility>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int MAX_N=2e5+5;
const int LOG=20;
vector<int>g[MAX_N];
int s[MAX_N];
int t[MAX_N];
int d[MAX_N];
int firstday[MAX_N];
int triplen[MAX_N];
bool state[MAX_N];

int parent[MAX_N][LOG];
int depth[MAX_N];
void dfs(int u,int par)
{
    parent[u][0]=par;
    for(int j=1;j<LOG;j++)
    {
        parent[u][j]=parent[parent[u][j-1]][j-1];
    }

    for(int v:g[u])
    {
        if(v==par)continue;
        depth[v]=depth[u]+1;
        dfs(v,u);
    }
}

int lc(int u,int v)
{
    if(depth[u]>depth[v])swap(u,v);

    for(int j=LOG-1;j>=0;j--)
    {
        if(depth[v]-(1<<j)>=depth[u])
        {
            v=parent[v][j];
        }
    }

    if(u==v)return u;

    for(int j=LOG-1;j>=0;j--)
    {
        if(parent[u][j]!=parent[v][j])
        {
            u=parent[u][j];
            v=parent[v][j];
        }
    }

    return parent[u][0];
}

vector<pair<long long,pair<int,short>>>events;
vector<int>ids[MAX_N];
vector<int>usedtowns;
bool used[MAX_N];

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
)
{
    int n=R.size()+1,m=D.size();
    for(int i=0;i<n-1;i++)
    {
        int u=R[i].first,v=R[i].second;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0,0);

    for(int i=0;i<m;i++)
    {
        firstday[i]=-1;
        d[i]=D[i];
        s[i]=S[i];
        t[i]=T[i];
        state[i]=I[i];
        if(state[i])firstday[i]=d[i];

        int lca=lc(s[i],t[i]);

        vector<int>path;
        int u=s[i],v=t[i];
        triplen[i]=depth[u]+depth[v]-2*depth[lca]+1;

        if(u!=lca && v!=lca)
        {
            while(u!=lca)
            {
                path.push_back(u);
                u=parent[u][0];
            }
            path.push_back(lca);

            vector<int>revpath;

            while(v!=lca)
            {
                revpath.push_back(v);
                v=parent[v][0];
            }
            reverse(revpath.begin(),revpath.end());

            for(int x:revpath)path.push_back(x);
        }
        else
        {
            if(depth[u]>depth[v])swap(u,v);

            while(v!=lca)
            {
                path.push_back(v);
                v=parent[v][0];
            }
            path.push_back(lca);

            if(s[i]==lca)reverse(path.begin(),path.end());
        }

        for(int id=0;id<path.size();id++)
        {
            events.push_back({d[i]+id,{path[id],i}});
        }
    }
    sort(events.begin(),events.end());

    bool inf=0;
    int prevday=-1;
    int id,town;

    int now;
    for(auto&[curday,vv]:events)
    {
        now=curday;
        if(prevday!=-1 && prevday!=curday)
        {
            for(int&town:usedtowns)
            {
                inf=0;
                for(int&id:ids[town])if(state[id])inf=1;

                if(!inf)continue;
                for(int&id:ids[town])
                {
                    if(!state[id])
                    {
                        firstday[id]=prevday;
                        state[id]=1;
                    }
                }
            }


            for(int&x:usedtowns)
            {
                ids[x].clear();
                used[x]=0;
            }
            usedtowns.clear();
        }

        tie(town,id)=vv;

        if(used[town]==0)
        {
            used[town]=1;
            usedtowns.push_back(town);
        }
        ids[town].push_back(id);


        prevday=curday;
    }


    for(int&town:usedtowns)
    {
        inf=0;
        for(int&id:ids[town])if(state[id])inf=1;

        if(!inf)continue;
        for(int&id:ids[town])
        {
            if(!state[id])
            {
                firstday[id]=prevday;
                state[id]=1;
            }
        }
    }


    for(int&x:usedtowns)
    {
        ids[x].clear();
        used[x]=0;
    }
    usedtowns.clear();


    vector<int>ans;
    for(int i=0;i<m;i++)
    {
        int f=firstday[i];
        if(f==-1){ans.push_back(0);continue;}

        ans.push_back(triplen[i]-(firstday[i]-d[i]));
    }

    return ans;
}
