#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;

int d[200001];
vector<int> v[200001];
int jump[200001][20];
void dfs(int i,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        d[nb]=d[i]+1;
        jump[nb][0]=i;
        dfs(nb,i);
    }
}

int lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    int j=d[x]-d[y];
    for(int i=0;i<20;i++)
    {
        if((1<<i)&j)
            x=jump[x][i];
    }

    if(x==y)return x;

    for(int i=19;i>=0;i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }
    return jump[x][0];
}

struct human
{
    long long d;
    int ver,id;
    human(){}
    human(int v,long long _d,int i)
    {
        ver=v;
        d=_d;
        id=i;
    }
};
bool cmp(human h1,human h2)
{
    return h1.d<h2.d;
}


long long u[200001];
long long uv[200001];

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
)

{
    for(int i=0;i<R.size();i++)
    {
        v[R[i].first].push_back(R[i].second);
        v[R[i].second].push_back(R[i].first);
    }

    dfs(0,-1);

    for(int j=1;j<20;j++)
    {
        for(int i=0;i<=R.size();i++)
        {
            jump[i][j]=jump[jump[i][j-1]][j-1];
        }
    }

    vector<human> p;

    for(int i=0;i<S.size();i++)
    {
        u[i]=I[i];
        int s=S[i],t=T[i];
        int l=lca(s,t);
        long long d=D[i];

        vector<int> in,out;

        while(s!=l)
        {
            in.push_back(s);
            s=jump[s][0];
        }

        while(t!=l)
        {
            out.push_back(t);
            t=jump[t][0];
        }

        in.push_back(l);
        //cout<<i<<"!! ";

        for(int j=0;j<in.size();j++)
        {
            //cout<<d<<" ";
            p.push_back({in[j],d,i});
            d++;
        }

        for(int j=out.size()-1;j>=0;j--)
        {
            //cout<<d<<" ";
            p.push_back({out[j],d,i});
            d++;
        }
        //cout<<endl;
    }

    sort(p.begin(),p.end(),cmp);
    vector<int> ans(S.size());
    int i=0;
    while(i<p.size())
    {
        long long d=p[i].d;
        int j=i;
        while(j+1<p.size()&&p[j+1].d==p[i].d)j++;

        for(int x=i;x<=j;x++)
        {
            if(u[p[x].id])
                uv[p[x].ver]=p[x].d;
        }

        for(int x=i;x<=j;x++)
        {
            if(uv[p[x].ver]==d)
                u[p[x].id]=1;
            
            if(u[p[x].id])
                ans[p[x].id]++;
        }

        i=j+1;
    }

    return ans;
}
