#include "infection.h"
#include <bits/stdc++.h>
#define NMAX 150000
#define LOG 20
using namespace std;

vector<int> tree[NMAX];
int n, m, depth[NMAX], anc[LOG][NMAX];

void dfs(int node, int parent)
{
    anc[0][node]=parent;
    for(auto& next : tree[node])
    {
        if(next==parent) continue;
        depth[next]=1+depth[node];
        dfs(next, node);
    }
}

void precalc()
{
    for(int e=1; e<LOG; e++)
    {
        for(int i=0; i<n; i++)
            anc[e][i]=anc[e-1][anc[e-1][i]];
    }
}

int up(int node, int k)
{
    for(int e=LOG-1; e>=0; e--)
    {
        if((1<<e)<=k)
        {
            k-=(1<<e);
            node=anc[e][node];
        }
    }
    return node;
}

int lca(int node1, int node2)
{
    if(depth[node1]<depth[node2]) swap(node1, node2);
    node1=up(node1, depth[node1]-depth[node2]);
    if(node1==node2) return node1;
    for(int e=LOG-1; e>=0; e--)
    {
        if(anc[e][node1]!=anc[e][node2])
        {
            node1=anc[e][node1];
            node2=anc[e][node2];
        }
    }
    return anc[0][node1];
}

vector<int> solve(vector<pair<int, int>> r, vector<long long> d, vector<int> s, vector<int> t, vector<bool> inf)
{
    n=r.size()+1;
    m=d.size();
    for(auto& [u, v] : r)
    {
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(0, -1);
    precalc();
    vector<int> ans;
    for(int i=0; i<m; i++)
    {
        if(!inf[i]) ans.push_back(0);
        else
        {
            int _lca=lca(s[i], t[i]);
            ans.push_back(depth[s[i]]+depth[t[i]]-2*depth[_lca]+1);
        }
    }
    return ans;
}