# include <iostream>
# include <vector>
# include <tuple>
# include <algorithm>
using namespace std;
# include "infection.h"
//# include "grader.cpp"

const long long INF=1e18;
const int MAX=2e5+11;

int n,m;
vector<int> adj[MAX];
vector<int> adj2[MAX];
long long D[MAX];
int S[MAX];
int T[MAX];
bool I[MAX];
long long inf[MAX];
int now[MAX];
long long len[MAX];
vector<int> party[MAX];

int ct;
int id[MAX];
int sz[MAX];
int up[MAX];
void dfs_init(int curr, int par)
{
    ct++;
    id[curr]=ct;
    sz[curr]=1;

    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;

        up[nxt]=curr;
        adj2[curr].push_back(nxt);
        dfs_init(nxt,curr);
        sz[curr]+=sz[nxt];
    }
}

bool inSubtree(int u, int v)
{
    return id[u]<=id[v] and id[v]<=id[u]+sz[u]-1;
}

int get_next(int u, int v)
{
    if(!inSubtree(u,v)) return up[u];

    int sz=adj2[u].size();
    int l=0,r=sz-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int t=adj2[u][mid];
        if(inSubtree(t,v)) return t;
        if(id[v]<id[t]) r=mid-1;
        else l=mid+1;
    }
    return -1;
}

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()+1,m=_D.size();
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        tie(u,v)=R[i];
        u++;v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=m;i++)
    {
        D[i]=_D[i-1];
        S[i]=_S[i-1]+1;
        T[i]=_T[i-1]+1;
        I[i]=_I[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        if(I[i]) inf[i]=D[i];
        else inf[i]=INF;
        now[i]=S[i];
        len[i]=D[i];
    }

    dfs_init(1,0);

    vector<pair<long long,int>> toAdd;
    for(int i=1;i<=m;i++) toAdd.push_back({D[i],i});
    sort(toAdd.begin(),toAdd.end());
    reverse(toAdd.begin(),toAdd.end());

    long long t=-1,cnt=0;
    while(true)
    {
        if(toAdd.size()==0) break;

        t=toAdd.back().first;
        vector<pair<long long,int>> toAdd2;
        while(toAdd.size()>0)
        {
            long long d,i;
            tie(d,i)=toAdd.back();
            //cout<<t<<"->"<<d<<" "<<i<<"\n";
            if(d==t)
            {
                toAdd.pop_back();
                party[now[i]].push_back(i);
                cnt++;
                if(now[i]!=T[i])
                {
                    //cout<<now[i]<<" "<<Data[i].t<<"->"<<get_next(now[i],Data[i].t)<<"\n";
                    now[i]=get_next(now[i],T[i]);
                    len[i]++;
                    toAdd2.push_back({t+1,i});
                }
            }
            else break;
        }

        for(int i=1;i<=n;i++)
        {
            bool f=0;
            for(int x: party[i]) if(inf[x]!=INF) f=1;
            if(f) for(int x: party[i]) inf[x]=min(inf[x],t);
            party[i].clear();
        }

        for(pair<long long,int> pa: toAdd2) toAdd.push_back(pa);
    }

    vector<int> ans;
    for(int i=1;i<=m;i++)
    {
        if(inf[i]==INF) ans.push_back(0);
        else ans.push_back(len[i]-inf[i]+1);
    }

    return ans;
}
