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

using namespace std;

typedef long long ll;

#ifndef GIGO_DEBUG
#define cerr if(false)cerr
#endif // GIGO_DEBUG

int n, m, mxLogDepth;

void dfs_root(int curr, int prev, const vector<vector<int>>& G, vector<int>& par, vector<int>& depth){
    if(prev == -1){
        depth[curr] = 0;
        par[curr] = curr;
    }else{
        depth[curr] = depth[prev]+1;
        par[curr] = prev;
    }
    for(int nxt : G[curr]){
        if(nxt == prev){ continue; }
        dfs_root(nxt, curr, G, par, depth);
    }
}

void prepLca(int root, const vector<vector<int>>& G, const vector<int>& par, const vector<int>& depth, vector<vector<int>>& kpar){
    for(int i = 0; i < n; i++){
        kpar[i][0] = par[i];
    }
    for(int k = 1; k <= mxLogDepth; k++){
        for(int i = 0; i < n; i++){
            kpar[i][k] = kpar[ kpar[i][k-1] ][k-1];
        }
    }
}

int mxLogFit(int x){
    int ret = 0;
    while((1<<ret) <= x){ ret++; }
    return ret-1;
}

int getLca(int u, int v, const vector<vector<int>>& kpar, const vector<int>& depth){
    int u2 = u, v2 = v;
    if(depth[u] > depth[v]){ swap(u, v); }
    while(depth[v] > depth[u]){
        int diff = depth[v] - depth[u];
        int mxlf =  mxLogFit(depth[v] - depth[u]);
        int newV =  kpar[v][ mxLogFit(depth[v] - depth[u]) ];
        v = newV;
    }

    int k = 0;
    while(kpar[u][k] != kpar[v][k]){
        cerr << "u: " << u << ", v: " << v << ", k=" << k << ", kpar=" << kpar[u][k] << '\n';
        k++;
    }

    int lca = kpar[u][k];
    cerr << "lca(" << u2 << ", " << v2 << ") = " << lca << '\n';
    return lca;
}

int dist(int u, int v, const vector<vector<int>>& kpar, const vector<int>& depth){
    int lca = getLca(u, v, kpar, depth);
    return depth[u] + depth[v] - 2*depth[lca];
}

vector<int> solve(vector<pair<int, int>> R, vector<ll> D, vector<int> S, vector<int> T, vector<bool> I) {
    n = R.size()+1;
    m = D.size();

    int root = 0;
    vector<vector<int>> G(n);
    for(int i = 0; i < R.size(); i++){
        int u = R[i].first, v = R[i].second;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<int> par(n), depth(n);
    dfs_root(0, -1, G, par, depth);



    int mxDepth = *max_element(depth.begin(), depth.end());
    mxLogDepth = 0;
    while((1<<mxLogDepth) <= mxDepth){ mxLogDepth++; }
    cerr << "mxdep: " << mxDepth << ", mxLD: " << mxLogDepth << '\n';

    vector<vector<int>> kpar(n);
    for(int i = 0; i < n; i++){
        kpar[i] = vector<int>(mxLogDepth+1); /// +1 FAAAH
    }

    prepLca(root, G, par, depth, kpar);

    for(int i = 0; i < n; i++){
        cerr << i << ": \n";
        for(int k = 0; k < mxLogDepth; k++){
            cerr << kpar[i][k] << ' ';
        }
        cerr << '\n';
    }

    vector<int> sickTime(m);
    for(int i = 0; i < m; i++){
        if(I[i]){
            sickTime[i] = dist(S[i], T[i], kpar, depth)+1;
        }
    }
    return sickTime;
}
