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

using namespace std;
using ll = long long;
const int NMAX = 150001;

vector<int> g[NMAX];
vector<int> drum;
int f[NMAX];
int niv[NMAX];

bool det_drumu(int nod, int f, int dr){
    drum.push_back(nod);
    if(nod == dr){
        return 1;
    }
    for(const int &x : g[nod]){
        if(x == f) continue;
        if( det_drumu(x, nod, dr) ) return 1;
    }
    drum.pop_back();
    return 0;
}

void dfs(int nod){
    for(const int &x : g[nod]){
        if(x == f[nod]) continue;
        f[x] = nod;
        niv[x] = niv[nod] + 1;
        dfs(x);
    }
}

vector<int> solve(
    vector<pair<int, int>> r,
    vector<long long> d,
    vector<int> s,
    vector<int> t,
    vector<bool> infect
) {

    int n = r.size() + 1;
    for(int i = 0; i < n - 1; i++){
        g[ r[i].first ].push_back(r[i].second);
        g[ r[i].second ].push_back(r[i].first);
    }

    f[0] = 0;
    niv[0] = 1;

    dfs(0);

    //cout << "F : ";
    //for(int i = 0; i < n; i++) cout << f[i] << " ";
    //cout << '\n';

    int lg = log2(n) + 1;
    int lf[n][lg];

    for(int i = 0; i < n; i++) lf[i][0] = f[i];
    for(int j = 1; j < lg; j++){
        for(int i = 0; i < n; i++){
            lf[i][j] = lf[ lf[i][j - 1] ][j - 1];
        }
    }

    vector<int> sol;
    int m = d.size(); // s4 in care nu se intersecteaza
    for(int ii = 0; ii < m; ii++){
        if(!infect[ii]){
            sol.push_back(0);
            continue;
        }

        int a = s[ii], b = t[ii];
        int aa = a, bb = b;

        int len = niv[a] + niv[b];
        //cout << "init " << niv[a] << " " << niv[b] << '\n';
        if(niv[a] > niv[b]) swap(a, b);

        // il aduc pe b la niv lui a
        for(int it = lg - 1; it >= 0; it--){
            if(niv[ lf[b][it] ] >= niv[a]){
                b = lf[b][it];
            }
        }

        if(a == b){
            sol.push_back( abs(niv[aa] - niv[bb]) + 1 );
        }

        for(int it = lg - 1; it >= 0; it--){
            if(lf[a][it] == lf[b][it]) continue;
            a = lf[a][it];
            b = lf[b][it];
        }


        a = lf[a][0];
        //cout << "lca = " << a << '\n';
        len -= niv[a] * 2;
        sol.push_back(len + 1);
    }

    return sol;
}