#include <bits/stdc++.h>
#include "infection.h"
#define ll long long
using namespace std;

vector<int> adj[150005];
int bl[19][150005], par[150005], lev[150005];

void dfs(int u = 1, int p = 0){
    par[u] = bl[0][u] = p;
    lev[u] = lev[p] + 1;
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if(lev[u] < lev[v]) swap(u, v);
    int dif = lev[u] - lev[v];
    for(int b = 0; b < 19; b++){
        if(dif & (1 << b))
            u = bl[b][u];
    }
    if(u == v) return u;
    for(int b = 18; b >= 0; b--){
        if(bl[b][u] != bl[b][v]){
            u = bl[b][u];
            v = bl[b][v];
        }
    }
    return par[u];
}

vector<int> solve(vector<pair<int, int>> r, vector<long long> d, vector<int> s, vector<int> t, vector<bool> inf){
    int n = r.size() + 1, m = d.size();
    for(int i = 0; i < n - 1; i++){
        auto [u, v] = r[i];
        u++;
        v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs();
    for(int b = 1; b < 19; b++){
        for(int i = 1; i <= n; i++){
            bl[b][i] = bl[b - 1][bl[b - 1][i]];
        }
    }
    vector<int> ans;
    for(int i = 0; i < m; i++){
        if(inf[i] == 0) ans.push_back(0);
        else{
            s[i]++;
            t[i]++;
            ans.push_back(lev[s[i]] + lev[t[i]] - 2 * lev[lca(s[i], t[i])] + 1);
        }
    }
    return ans;
}
