#include "infection.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> res;
vector<ll> depth;
vector<vector<ll>> connections, binup;
ll lg;

ll dist(ll a, ll b)
{
    ll res = 0;
    if(depth[b] < depth[a]) swap(a, b);
    for(ll i = lg; i >= 0; i--)
    {
        if(binup[i][b] == -1) continue;
        // cout << binup[i][b];
        if(depth[binup[i][b]] >= depth[a])
        {
            b = binup[i][b];
            res += 1ll << i;
            // cout << "add1 " << (1ll << i);
        }
    }
    if(a != b)
    {
        for(ll i = lg; i >= 0; i--)
        {
            if(binup[i][a] == -1 || binup[i][b] == -1) continue;
            if(binup[i][a] != binup[i][b])
            {
                a = binup[i][a];
                b = binup[i][b];
                res += 2*(1ll << i);
                // cout << "add2 " << 2*(1ll << i);
            }
        }
        res += 2;
    }
    return res;
}

void dfs(ll i, ll p, ll d)
{
    binup[0][i] = p;
    depth[i] = d;
    for(ll num : connections[i])
    {
        if(num == p) continue;
        dfs(num, i, 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
)
{
    ll amount = R.size()+1;
    lg = 63 - __builtin_clzll(amount);
    connections.resize(amount);
    binup.assign(lg+1, vector<ll>(amount, -1));
    depth.resize(amount);
    for(ll i = 0; i < amount-1; i++)
    {
        connections[R[i].first].push_back(R[i].second);
        connections[R[i].second].push_back(R[i].first);
    }
    dfs(0, -1, 0);
    for(ll i = 1; i <= lg; i++)
    {
        for(ll j = 0; j < amount; j++)
        {
            if(binup[i-1][j] == -1) binup[i][j] = -1;
            else binup[i][j] = binup[i-1][binup[i-1][j]];
        }
    }
    ll people = (ll)S.size();
    res.resize(people);
    bool spaced = true;
    for(ll i = 0; i < people; i++)
    {
        
        if(D[i] != 1e6 * i)
        {
            spaced = false;
        }
    }
    if(spaced || true)
    {
        for(ll i = 0; i < people; i++)
        {
            res[i] = I[i] ? dist(S[i], T[i])+1 : 0;
        }
    }
    return res;
}
