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

using namespace std;

int n, m;

vector<int> depth, jump, par;
vector<vector<int>> graph;

int ddist(int a, int b) {
    return max(depth[a], depth[b]) - min(depth[a], depth[b]);
}

void dfs(int v, int p, int d) {
    par[v] = p;
    depth[v] = d;

    jump[v] = p;
    if (ddist(p, jump[p]) == ddist(jump[p], jump[jump[p]])) jump[v] = jump[jump[p]];

    for (int u : graph[v]) {
        if (u == p) continue;
        dfs(u, v, d+1);
    }
}

int jumpto(int v, int d) {
    int vx = v;
    while (depth[vx] > d) {
        if (depth[jump[vx]] < d) vx = par[vx];
        else vx = jump[vx];
    }
    return vx;
}

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

    ax = jumpto(ax, depth[bx]);

    while (ax != bx) {
        if (jump[ax] == jump[bx]) {
            ax = par[ax];
            bx = par[bx];
        } else {
            ax = jump[ax];
            bx = jump[bx];
        }
    }

    return ax;
}

vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {
    n = R.size()+1;
    m = I.size();

    depth.assign(n, 0);
    jump.assign(n, 0);
    par.assign(n, 0);
    graph.assign(n, vector<int>());

    for (pair<int, int> edge : R) {
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }

    dfs(0, 0, 0);

    vector<int> daysSick(m, 0);

    for (int i = 0; i < m; i++) {
        if (I[i]) {
            int l = lca(S[i], T[i]);
            daysSick[i] = ddist(l, S[i]) + ddist(l, T[i]) + 1;
        }
    }

    return daysSick;
}

// signed main() {
//     int n, m;

//     cin >> n;
//     cin >> m;

//     vector<pair<int, int>> edges = {};
//     vector<long long> day;
//     vector<int> start;
//     vector<int> target;
//     vector<bool> infected;

//     for (int i = 0; i < n - 1; i++) {
//         int u, v;
//         cin >> u >> v;
//         edges.emplace_back(u, v);
//     }

//     for (int i = 0; i < m; i++) {
//         long long _d, _s, _t, _i;
//         cin >> _d >> _s >> _t >> _i;
//         day.push_back(_d);
//         start.push_back(_s);
//         target.push_back(_t);
//         infected.push_back(_i);
//     }

//     const auto ans = solve(edges, day, start, target, infected);
//     for (const auto it : ans) {
//         cout << it << endl;
//     }

//     return 0;
// }
