#include "infection.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <deque>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;

constexpr int K = 20;

// struct node {
//     ll d;
//     int s, t;
//     bool i;
//     bool operator<(const node &x) {
//         return x.d < d;
//     }
//     bool operator>(const node &x) {
//         return x.d > d;
//     }
// };
//
// struct node2 {
//     int v, t;
//     bool i;
//     bool operator<(const node2 &x) {
//         return x.v < v;
//     }
// };

int timer;
int _n, _m; /// WARNING: M is not edge's count
vector<ll> D;
vector<int> S, T, pa, inT, outT, lvl, cnt, ans;
vector<bool> I;
vector<pair<int, int>> R;
vector<vector<int>> g, up;

void systemd() {
    timer++;
    _n = R.size() + 1;
    _m = D.size();
    pa.resize(_n);
    inT.resize(_n);
    outT.resize(_n);
    lvl.resize(_n);
    cnt.assign(_n, 0);
    ans.assign(_m, 0);
    g.clear();
    g.resize(_n + 1);
    up.resize(K, vector<int>(_n));
}

void dfs(int v, int par) {
    inT[v] = timer++;
    for (const auto &u : g[v]) {
        if (u == par)
            continue;
        pa[u] = v;
        lvl[u] = lvl[v] + 1;
        dfs(u, v);
    }
    outT[v] = timer;
}

inline bool is_ans(int v, int l) {
    return (inT[l] <= inT[v] && outT[v] <= outT[l]);
}

int upv(int v, int cnt) {
    for (int k = 0; k < K; k++) {
        if ((1 << k) & cnt) {
            v = up[k][v];
        }
    }
    return v;
}

int nxtt(int v, int t) {
    if (is_ans(t, v)) {
        // cerr << "T: " << t << endl;
        // cerr << upv(t, lvl[t] - lvl[v] - 1) << endl;
        return upv(t, lvl[t] - lvl[v] - 1);
    }
    return pa[v];
}

void build_lca() {
    for (int v = 0; v < _n; v++) {
        up[0][v] = pa[v];
    }
    for (int i = 1; i < K; i++) {
        for (int v = 0; v < _n; v++) {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
    }
}

int lca(int v, int u) {
    if (lvl[v] > lvl[u])
        swap(v, u);
    if (is_ans(u, v)) {
        return v;
    }
    if (is_ans(v, u))
        return u;
    int k = lvl[u] - lvl[v];
    for (int i = 0; i < K; i++) {
        if ((1 << i) & k) {
            u = up[i][u];
        }
    }
    for (int i = K - 1; i >= 0; --i) {
        if (up[i][v] != up[i][u]) {
            v = up[i][v];
            u = up[i][u];
        }
    }
    assert(up[0][v] == up[0][u]);
    return up[0][v];
}

int dist(int u, int v) {
    int l = lca(u, v);
    // cerr << "Dist: " << u << ' ' << v << ' ' << lvl[u] + lvl[v] - (2 * lvl[l]) << endl;
    // cerr << "LCAAA: " << u << ' ' << v << ' ' << l << endl;
    return lvl[u] + lvl[v] - (2 * lvl[l]);
}

void bfs() {
    int timer = 0;
    set<array<ll, 5>> st;
    for (ll i = 0; i < _m; i++) {
        st.insert({D[i], S[i], T[i], I[i], i});
    }
    deque<array<ll, 4>> nxt;
    while (!st.empty() || !nxt.empty()) {
        array<ll, 5> cur = {timer, 0, 0, 0, 0};
        auto it = st.lower_bound(cur);
        if (nxt.empty())
            timer = (*it)[0];
        // cerr << "Timer; " << timer << endl;
        deque<array<ll, 4>> dq;
        dq.swap(nxt);
        while (it != st.end()) {
            if ((*it)[0] > timer) {
                break;
            }
            dq.push_back({(*it)[1], (*it)[2], (*it)[3], (*it)[4]});
            auto cur = it;
            it++;
            st.erase(cur);
        }
        assert(dq.size());
        auto _dq = dq;
        while (!dq.empty()) {
            const auto [v, t, i, id] = dq.front();
            // cerr << "V: " << v << endl;
            dq.pop_front();
            if (i) {
                cnt[v]++;
            }
        }
        dq = _dq;
        set<int> vc;
        while (!dq.empty()) {
            const auto [v, t, i, id] = dq.front();
            dq.pop_front();
            int u = nxtt(v, t);
            if (i)
                vc.insert(v);
            // cerr << "V, T, U, id, i: " << v << ' ' << t << ' ' << u << ' ' << id << ' ' << i << endl;
            if (i) {
                assert(cnt[v]);
            }
            if (cnt[v] > 0) {
                ans[id] = max(ans[id], dist(v, t) + 1);
            }
            if (v != t)
                nxt.push_back({u, t, (bool)(cnt[v]), id});
        }
        for (int v : vc) {
            cnt[v] = 0;
        }
        timer++;
    }
}

void brute() {
    deque<array<int, 3>> dq;
}

std::vector<int> solve(
    std::vector<std::pair<int, int>> _R,
    std::vector<long long> _D,
    std::vector<int> _S,
    std::vector<int> _T,
    std::vector<bool> _I) {
    R = _R, D = _D, S = _S, T = _T, I = _I;
    systemd();
    for (const auto &[u, v] : R) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // cerr << "input is OK\n";
    dfs(0, -1);
    // cerr << "DFS is OK\n";
    build_lca();
    // cerr << "Build_lca is OK\n";
    bfs();
    // cerr << "bfs is OK\n";
    return ans;
}
/*
9 2
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
0 5 0 1
0 8 3 0
 */
