#include<bits/stdc++.h>
#include "infection.h"
using namespace std;
using ll=long long;

const ll N=1.5e5+55,inf=1e18;
vector<ll>g[N];
ll up[N][20],tin[N],tout[N],d[N],ti,n,m;

void dfs(ll u,ll p){
    up[u][0]=p;
    tin[u]=++ti;
    for(ll v:g[u]){
        if(!(v^p))continue;
        d[v]=d[u]+1;
        dfs(v,u);
    }
    tout[u]=++ti;
}

bool iznad(ll u,ll v){
    return(tin[u]<=tin[v]&&tout[u]>=tout[v]);
}

ll lca(ll u,ll v){
    if(iznad(u,v))return u;
    if(iznad(v,u))return v;
    for(int j=19;j>=0;--j){
        if(up[u][j]&&!iznad(up[u][j],v))u=up[u][j];
    }
    return up[u][0];
}

ll dist(ll u,ll v){
    return d[u]+d[v]-2*d[lca(u,v)];
}

vector<ll>put[N];
ll ans[N],ima[N];
vector<array<ll,2>>abc[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
){
    m=S.size();
    n=R.size()+1;

    for(int i=0;i<N;++i){
        g[i].clear();
        for(int j=0;j<20;++j)up[i][j]=0;
        tin[i]=tout[i]=0;
        d[i]=0;
        put[i].clear();
        ans[i]=0;
        ima[i]=I[i];
    }
    ti=0;

    for(auto[u,v]:R){
        ++u,++v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,0);
    for(int j=1;j<20;++j){
        for(int i=1;i<=n;++i)
            up[i][j]=up[up[i][j-1]][j-1];
    }

    for(int i=0;i<m;++i){
        ll u=S[i]+1,v=T[i]+1;
        ll lc=lca(u,v);
        if(u!=lc)put[i].push_back(u);
        while(u!=lc){
            u=up[u][0];
            put[i].push_back(u);
        }
        vector<ll>nesto;
        if(v!=lc)nesto.push_back(v);
        while(v!=lc){
            v=up[v][0];
            nesto.push_back(v);
        }
        nesto.push_back(v);
        reverse(nesto.begin(),nesto.end());
        for(ll xx:nesto)put[i].push_back(xx);
    }

    for(int tk=0;tk<=n;++tk){
        for(int i=0;i<=n;++i){
            abc[i].clear();
        }
        for(int i=0;i<m;++i){
            if(tk<put[i].size()){
                abc[put[i][tk]].push_back({i,ima[i]});
            }
        }
        for(int i=1;i<=n;++i){
            bool Ima=0;
            for(auto[koi,ii]:abc[i]){
                Ima|=ii;
            }
            for(int j=0;j<abc[i].size();++j)
                abc[i][j][1]|=Ima;
            for(auto[koi,ii]:abc[i]){
                ima[koi]|=ii;
                ans[koi]+=ii;
            }
        }
    }

    vector<int>ret;
    for(int i=0;i<m;++i)
        ret.push_back(ans[i]);

    return ret;
}
