#include "infection.h"
#include <bits/stdc++.h>
#define out(x) #x<<" = "<<x<<" "
using namespace std;

const int MAX = 2 * 1e5 + 10;
int head[MAX], pos[MAX], heavy[MAX], dep[MAX], sz[MAX], par[MAX], n;
int sp[19][MAX];
vector<int> rrr[MAX];

void dfs(int x, int p){
    sz[x] = 1;
    heavy[x] = -1;
    par[x] = p;
    dep[x] = dep[p] + 1;

    for(int i: rrr[x]){
        if(i == p) continue;
        dfs(i, x);
        sz[x] += sz[i];
        if(heavy[x] == -1 || sz[i] > sz[heavy[x]]) heavy[x] = i;
    }
}

int curr;

void sp_table(){
    for(int i = 1; i < n; i++){
        sp[0][i] = par[i];
    }

    for(int i = 1; i <= 18; i++){
        for(int j = 1; j < n; j++){
            //if(dep[j] <= (1 << i)) continue;
            sp[i][j] = sp[i - 1][sp[i - 1][j]];
            //if(i <= 2) cout<<sp[i][j]<<" ";
        }
        //cout<<endl;
    }
}

int find_lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 18; i >= 0; i--){
        //if(dep[x] <= (1 <<i)) continue;
        if(dep[sp[i][x]] < dep[y]) continue;
        x = sp[i][x];
    }
    while(par[x] != par[y]){
        for(int i = 18; i>= 0; i--){
            //if(dep[x] <= (1<<i)) continue;
            if(sp[i][x] == sp[i][y]) continue;
            x = sp[i][x];
            y = sp[i][y];
        }
    }
    return par[x];
}


vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    //reset();
    for(int i = 0; i < R.size(); i++){
        rrr[R[i].first].push_back(R[i].second);
        rrr[R[i].second].push_back(R[i].first);
        n = max(n, R[i].first);
        n = max(n, R[i].second);
    }
    n ++;
    dfs(0, 0);
    sp_table();

    vector<int> ans;
    for(int i = 0; i < I.size(); i++){
        ans.push_back(0);
        if(!I[i]) continue;

        int l = find_lca(S[i], T[i]);
        int a = S[i], b = T[i];
        ans[i] = dep[a] + dep[b] - 2  * dep[l] + 1;
    }


    return ans;
}
