#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAXN=150009;
vector<int> ans;
long long dist[MAXN],father[MAXN];
long long dp[MAXN][20];
vector<int> edg[MAXN];
long long N,M;

int f(int n,int p)
{
    if(dp[n][p]!=-1)return dp[n][p];
    if(p==0)return dp[n][p]=father[n];
    return dp[n][p]=f(f(n,p-1),p-1);
}

int lca(int a,int b)
{
    if(dist[a]>dist[b])swap(a,b);

    for(int i=19;i>=0;i--)
    {
        if((dist[b]-dist[a])&(1LL<<i))b=f(b,i);
    }

    if(a==b)return a;

    for(int i=19;i>=0;i--)
    {
        if(f(a,i)!=f(b,i))
        {
            a=f(a,i);
            b=f(b,i);
        }
    }

    return father[a];
}

int calcD(int a,int b)
{
    int c=lca(a,b);
    return dist[a]+dist[b]-2*dist[c]+1;
}

void dfs(int start,int f,int d)
{
    dist[start]=d;
    father[start]=f;

    for(auto i:edg[start])
    {
        if(i!=f)dfs(i,start,d+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
)
{
    memset(dp,-1,sizeof(dp));
    N=R.size()+1;
    M=I.size();
    for(auto i:R)
    {
        edg[i.first].push_back(i.second);
        edg[i.second].push_back(i.first);
    }

    dfs(0,0,0);

    for(int i=0;i<M;i++)
    {
        ans.push_back(I[i]*calcD(S[i],T[i]));
    }

    return ans;
}
