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

using namespace std;

typedef long long ll;

const int MAXN = 150005, LOG = 20;
int up[MAXN][LOG];
int depth[MAXN];
int n, m;

vector<int> con[MAXN];

void dfs(int curr, int par){
    up[curr][0] = par;
    for (int i = 1; i < LOG; i++)
        up[curr][i] = up[up[curr][i - 1]][i - 1];
    
    for (auto i : con[curr])
        if (i != par)
            depth[i] = depth[curr] + 1, dfs(i, curr);
}

int lca(int a, int b){
    if (depth[a] < depth[b])
        swap(a, b);

    for (int j = LOG - 1; j >= 0; j--)
        if (depth[a] - (1 << j) >= depth[b])
            a = up[a][j];
        
    if (a == b) return a;

    for (int j = LOG - 1; j >= 0; j--)
        if (up[a][j] != up[b][j])
            a = up[a][j], b = up[b][j];

    return up[a][0];
}

int dist(int a, int b){
    return depth[a] + depth[b] - (2 * depth[lca(a, b)]);
}

vector<int> solve(vector<std::pair<int, int>> r, vector<ll> d, vector<int> s, vector<int> t, vector<bool> inf) {
    n = r.size() + 1, m = d.size();

    for (int i = 0; i < n - 1; i++)
        con[r[i].first].push_back(r[i].second), con[r[i].second].push_back(r[i].first);

    dfs(1, 1);

    vector<int> res;

    for (int i = 0; i < m; i++) {
        if (inf[i])
            res.push_back(dist(s[i], t[i]) + 1);
        else
            res.push_back(0);
    }

    return res;
}
