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

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

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

    if(x==y)return x;

    for(long long 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;
    long long ver,id;
    human(){}
    human(long long v,long long _d,long long 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(long long 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(long long j=1;j<20;j++)
    {
        for(long long i=0;i<=R.size();i++)
        {
            jump[i][j]=jump[jump[i][j-1]][j-1];
        }
    }

    vector<human> p;
    vector<int> ans(S.size());
    for(long long i=0;i<S.size();i++)
    {
        if(I[i])u[i]=1;
        else u[i]=0;
        long long s=S[i],t=T[i];
        long long l=lca(s,t);
        long long d=D[i];

        vector<long long> 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(long long j=0;j<in.size();j++)
        {
            //cout<<d<<" ";
            p.push_back({in[j],d,i});
            d++;
        }

        for(long long 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);


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

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

            if(u[p[x].id]==1)
                ans[p[x].id]++;
        }

        i=j;
    }

    return ans;
}
