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

using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
#define endl '\n'

vector <vector <int> > g;
vector <vector <int> > par;
vector <int> tin, tout;
int t = 0;

void dfs(int v,int p){
    par[v][0] = v;
    par[v][1] = p;
    t++;
    tin[v] = t;

    for(int i = 2;i <= 20;i++){
        par[v][i] = par[par[v][i - 1]][i - 1];
    }

    for(int i = 0;i < (int)g[v].size();i++){
        int u = g[v][i];
        if(u == p) continue;

        dfs(u , v);
    }
    t++;
    tout[v] = t;
}

bool is_par(int a ,int b){
    if(tin[a] <= tin[b] && tout[a] >= tout[b]){
        return true;
    }
    return false;
}

int dis(int a , int b , int sum){
    int j = 0;
    for(int i = 1;i < 20;i++){
        if(is_par(par[a][i] , b)){
            break;
        }
        j = i;
    }

    if(j == 0){
        return sum;
    }
    else{
        return dis(par[a][j] , b , sum + pow(2 , j));
    }
}

int lca(int a ,int b){
    int j = 0;
    for(int i = 1;i < 20;i++){
        if(is_par(par[a][i] , b)){
            break;
        }
        j = i;
    }

    if(j == 0){
        return par[a][1];
    }
    return lca(par[a][j] , b);
}

std::vector<int> solve(
    std::vector<std::pair<int, int> > edge,
    std::vector<long long> d,
    std::vector<int> s,
    std::vector<int> t,
    std::vector<bool> i1
) {


    int n = edge.size() + 1;
    g.resize(n  +1);
    tin.resize(n + 1);
    tout.resize(n + 1);



    for(int i = 0;i < n - 1;i++){
        g[edge[i].ff].pb(edge[i].ss);
        g[edge[i].ss].pb(edge[i].ff);
    }

    int m = d.size();

    vector <int> c(m);

    for(int i = 0;i < m;i++){
        if(i1[i]){
            c[i] = 1;
        }
    }

    par.resize(n + 1, vector <int> (25));
    cout<<"here"<<endl;
    dfs(1 , 1);

    vector <int> ans(m);

    for(int i = 0;i < m;i++){
        //cout<<i<<endl;
        int lc;
        int a = s[i];
        int b = t[i];
        bool f = 0;
        if(is_par(a , b)){
                lc = a;
        }
        else if(is_par(b , a)){
                lc = b;
        }
        else{
            lc = lca(s[i] , t[i]);
            f = 1;
        }
        if(c[i] == 1){
            ans[i] = dis(a , lc , 0) + dis(b , lc , 0);
        }
        
        if(f){
            ans[i]++;
        }
    }

    return ans;
}
