#include <bits/stdc++.h>
#include "infection.h"
using namespace std;
const int nmax = 150000, bmax = 18;
vector <pair<int, int>> r;
vector <long long> d;
vector <int> s,t;
vector <bool> p;
vector <int> g[nmax + 1];
bool ok[nmax + 1];
int tur[nmax * 2 + 1], k, rmq[nmax * 2 + 1][bmax + 1], poz[nmax + 1], niv[nmax + 1];
void dfs(int nod, int t)
{
    tur[++k] = nod;
    poz[nod] = k;
    for(auto x : g[nod])
    {
        if(x != t)
        {
            niv[x] = niv[nod] + 1;
            dfs(x, nod);
        }
        tur[++k] = nod;
    }
}
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)
{
    int n = R.size() + 1, m = D.size(), i ,j, lca;
    vector <int> sol(m);
    k = 0;
    for(auto x : R)
    {
        g[x.first].push_back(x.second);
        g[x.second].push_back(x.first);
    }
    dfs(1, -1);
    for(i = 0; i < m; i++)
    {
        rmq[i][0] = tur[i];
    }
    for(j = 1; j <= bmax; j++)
    {
        for(i = 0; i + (1 << j) < m; i++)
        {
            if(niv[tur[rmq[i][j - 1]]] <= niv[tur[rmq[i + (1 << (j - 1))][j - 1]]])
                rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
            else
                rmq[i][j] = rmq[i][j - 1];
        }
    }
    int x, y, st ,dr;
    for(i = 0; i < m; i++)
    {
        x = poz[S[i]];
        y = poz[T[i]];
        st = poz[S[i]];
        dr = poz[T[i]];
        if(x > y)
            swap(x, y);
        for(j = 0; x + (1 << j) <= y; j++);
        j--;
        if(niv[tur[rmq[st][j]]] <= niv[tur[rmq[dr - (1 << j)][j]]])
            lca = tur[rmq[dr - (1 << j)][j]];
        else
            lca = tur[rmq[st][j]];
        if(lca == S[i] || lca == T[i])
            sol[i] = abs(niv[S[i]] - niv[T[i]]);
        else
            sol[i] = niv[S[i]] + niv[T[i]] - niv[lca] * 2;
        sol[i] *= I[i];
    }
    return sol;
}
