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

using namespace std;

const long long MAXN=150000;
const long long LOG=24;

long long lift[MAXN+10][LOG];
long long par[MAXN+10];
long long dept[MAXN+10];
long long ans[MAXN+10];

long long in[MAXN+10];
long long out[MAXN+10];
long long tim=0;
vector<long long>tree[MAXN+10];

void dfs(long long x, long long p)
{
    tim++;
    in[x]=tim;
    for (auto next:tree[x])
    {
        if (p==next) continue;
        dept[next]=dept[x]+1;
        par[next]=x;
        dfs(next, x);
    }
    tim++;
    out[x]=tim;
}

struct info
{
    long long x;
    long long fin;
    long long zar;
    long long ind;
    long long day;
};

bool cmp(info x, info y)
{
    return x.x<y.x;
}
bool cmpd(info x, info y)
{
    return x.day<y.day;
}

vector<int> solve(
    vector<std::pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
)
{
    long long n=0;
    for (long long i=0; i<R.size(); i++)
    {
        tree[R[i].first+1].push_back(R[i].second+1);
        tree[R[i].second+1].push_back(R[i].first+1);
        n=max(n, R[i].second+1LL);
        n=max(n, R[i].first+1LL);
    }
    out[0]=1e9;
    dept[1]=1;
    dfs(1, 0);

    vector<info>podays;
    for (long long i=0; i<S.size(); i++)
    {
        podays.push_back({S[i]+1, T[i]+1, I[i], i, D[i]});
    }
    sort(podays.begin(), podays.end(), cmpd);
    long long pok=0;
    vector<info>v;
    while (1)
    {
        if (pok==podays.size()) break;

        v.push_back(podays[pok]);
        pok++;

        while (v.size())
        {
            long long mnday=1e15;
            for (long long i=0; i<v.size(); i++)
            {
                mnday=min(mnday, v[i].day);
            }

            while (pok<podays.size() && podays[pok].day==mnday)
            {
                v.push_back(podays[pok]);
                pok++;
            }

            sort(v.begin(), v.end(), cmp);
            long long mx=0;
            long long start=0;

            for (long long i=0; i<v.size(); i++)
            {
                if (v[i].day==mnday) mx=max(mx, v[i].zar);

                if (i==v.size()-1 || v[i].x!=v[i+1].x)
                {
                    if (mx==1)
                    {
                        for (long long j=start; j<=i; j++)
                        {
                            if (v[j].day==mnday) v[j].zar=1;
                        }
                    }
                    mx=0;
                    start=i+1;
                }
            }
            vector<info>sled;
            for (long long i=0; i<v.size(); i++)
            {
                if (mnday!=v[i].day)
                {
                    sled.push_back(v[i]);
                    continue;
                }

                ans[v[i].ind]+=v[i].zar;
                if (v[i].x==v[i].fin) continue;

                if (in[v[i].x]<=in[v[i].fin] && out[v[i].fin]<=out[v[i].x])
                {
                    for (auto next:tree[v[i].x])
                    {
                        if (next==par[v[i].x]) continue;

                        if (in[next]<=in[v[i].fin] && out[v[i].fin]<=out[next])
                        {
                            v[i].x=next;
                            break;
                        }
                    }
                }
                else
                {
                    v[i].x=par[v[i].x];
                }
                v[i].day++;
                sled.push_back(v[i]);
            }
            v=sled;
        }

    }


    vector<int>ret;







    for (long long i=0; i<S.size(); i++)
    {
        ret.push_back(ans[i]);
    }

    return ret;
}


