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

using namespace std;

vector<int> uf;

int uff(int a) {
    if (uf[a] != a) uf[a] = uff(uf[a]);
    return uf[a];
}

void ufu(int a, int b) {
    uf[uff(a)] = uff(b);
}

int n, m;

int getV(int isR, int isP, int v) {
    if (isR) return v;
    if (isP) return n + v;
    return 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;
}

int get_pos(int s, int g, int d) {
    int l = lca(s, g);
    if (d > ddist(s, l) + ddist(l, g) or d < 0) return -1;
    if (d <= ddist(s, l)) return jumpto(s, depth[s] - d);
    return jumpto(g, depth[l] + d - ddist(s, l));
}

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();

    int ufSize = n+m+1;
    uf.assign(ufSize, 0);
    depth.assign(n, 0);
    jump.assign(n, 0);
    par.assign(n, 0);
    graph.assign(n, vector<int>());

    vector<int> firstSick(m, -1);

    for (int i = 0; i < m; i++) {
        if (I[i]) firstSick[i] = 0;
    }

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

    dfs(0, 0, 0);

    priority_queue<int> days;

    for (int j = 0; j < m; j++) {
        days.push(-D[j]);
    }

    int lDay = -1;

    while (not days.empty()) {
        int i = -days.top();
        days.pop();

        if (i == lDay) continue;

        for (int j = 0; j < ufSize; j++) uf[j] = j;

        int cont = 0;
        for (int j = 0; j < m; j++) {
            int p = get_pos(S[j], T[j], i - D[j]);
            
            if (p == -1) continue;

            ufu(getV(1, 0, p), getV(0, 1, j));

            if (firstSick[j] <= i - D[j] and firstSick[j] != -1) ufu(getV(0, 1, j), getV(0, 0, 0));

            if (p != T[j] and (not cont)) {
                cont = 1;
                days.push(-1 - i);
            }
        }

        for (int j = 0; j < m; j++) {
            if (uff(getV(0, 1, j)) == uff(getV(0, 0, 0)) and firstSick[j] == -1) firstSick[j] = i - D[j];
        }

        lDay = i;
    }

    vector<int> daysSick(m, 0);

    for (int i = 0; i < m; i++) {
        if (firstSick[i] != -1) {
            int l = lca(S[i], T[i]);
            daysSick[i] = ddist(S[i], l) + ddist(T[i], l) - firstSick[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;
// }
