#include "infection.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > v, ba(18);
vector<int> pa, de;
int n, m, lg = 18;
void dfs(int i)
{
    for (auto& h : v[i])
    {
        if (h == pa[i])
            continue;
        pa[h] = i;
        de[h] = de[i] + 1;
        dfs(h);
    }
}
int lca(int a, int b)
{
    for (int i = lg - 1; i >= 0; i--)
    {
        if (de[a] - de[b] >= (1 << i))
            a = ba[i][a];
        if (de[b] - de[a] >= (1 << i))
            b = ba[i][b];
    }
    for (int i = lg - 1; i >= 0; i--)
    {
        if (ba[i][a] != ba[i][b])
        {
            a = ba[i][a];
            b = ba[i][b];
        }
    }
    if (a == b)
        return a;
    return ba[0][b];
}
vector<int> solve(vector<pair<int, int> > R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I)
{
    int i, j, k;
    long long a, b, c, d;
    n = R.size() + 1;
    m = D.size();
    v.resize(n);
    pa.resize(n);
    de.resize(n);
    for (auto& h : R)
    {
        v[h.first].push_back(h.second);
        v[h.second].push_back(h.first);
    }
    pa[0] = n;
    de[0] = 0;
    dfs(0);
    for (i = 0; i < lg; i++)
    {
        ba[i].resize(n + 1);
        for (j = 0; j <= n; j++)
        {
            if (!i)
            {
                if (j == n)
                    ba[i][j] = n;
                else
                    ba[i][j] = pa[j];
            }
            else
                ba[i][j] = ba[i - 1][ba[i - 1][j]];
        }
    }
    vector<int> U(m);
    for (i = 0; i < m; i++)
        U[i] = lca(S[i], T[i]);
    vector<int> an(m, 0);
    for (i = 0; i < m; i++)
    {
        if (I[i])
            an[i] = de[S[i]] + de[T[i]] - 2 * de[U[i]] + 1;
        else
            an[i] = 0;
    }
    return an;
}
