#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 150009, logMaxN = 18;
using ll = long long;
vector<int> adj[maxN];
vector<int> path[maxN];
int depth[maxN], par[maxN];
int sp[logMaxN][maxN];
ll stInf[maxN];
bitset<maxN> vis, infec;

void dfs(int cur) {
    vis[cur] = true;
    for (int son : adj[cur]) {
        if (!vis[son]) {
            par[son] = cur;
            depth[son] = depth[cur] + 1;
            dfs(son);
        }
    }
}
void initSp(int n) {
    for (int i = 0; i < n; i++) { sp[0][i] = par[i]; }
    for (int i = 1; i < logMaxN; i++) {
        for (int j = 0; j < n; j++) {
            if (sp[i - 1][j] == -1) { sp[i][j] = -1; }
            else { sp[i][j] = sp[i - 1][sp[i - 1][j]]; }
        }
    }
}
int getLCA(int a, int b) {
    if (depth[a] < depth[b]) { swap(a, b); }
    for (int i = logMaxN - 1; i >= 0; i--) {
    assert(a != -1 && b != -1);
        if (sp[i][a] == -1) { continue; }
        if (depth[a] - (1 << i) >= depth[b]) { a = sp[i][a]; }
    }
    assert(depth[a] == depth[b]);
    if (a == b) { return a; }
    for (int i = logMaxN - 1; i >= 0; i--) {
        assert(a != -1 && b != -1);
        if (sp[i][a] != sp[i][b]) {
            a = sp[i][a];
            b = sp[i][b];
        }
    }
    return par[a];
}

vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I) {

    for (auto e : R) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    int n = R.size() + 1, m = D.size();
    par[0] = -1;
    dfs(0);
    initSp(n);
    vector<int> ans(m);
    for (int i = 0; i < m; i++) {
        int lca = getLCA(S[i], T[i]);
        int tmp = S[i];
        while (tmp != par[lca]) {
            path[i].push_back(tmp);
            tmp = par[tmp];
        }
        int sz = path[i].size();
        tmp = T[i];
        while (tmp != lca) {
            path[i].push_back(tmp);
            tmp = par[tmp];
        }
        reverse(path[i].begin() + sz, path[i].end());
    }

//    for (int i = 0; i < m; i++) {
//        for (int x : path[i]) { cout << x << ' '; }
//        cout << '\n';
//    }

    for (int i = 0; i < m; i++) {
        stInf[i] = (I[i] ? D[i] : -1);
    }
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [D](int i1, int i2) { return D[i1] < D[i2]; });
    vector<int> active;
    ll day = 0, l = 0;
    infec = 0;
    while (l < m || active.size()) {
        if (active.size() == 0) { day = D[idx[l]]; }
        for (int i = 0; i < active.size(); i++) {
            if (D[active[i]] + path[active[i]].size() <= day) {
                active.erase(active.begin() + i);
                i--;
            }
        }
        while (l < m && D[idx[l]] <= day) {
            active.push_back(idx[l++]);
        }
        for (int i : active) {
            if (stInf[i] != -1) { infec[path[i][day - D[i]]] = true; }
        }
        for (int i : active) {
            if (stInf[i] == -1 && infec[path[i][day - D[i]]]) {
                stInf[i] = day;
            }
        }
        for (int i : active) {
            if (stInf[i] != -1) { infec[path[i][day - D[i]]] = false; }
        }
        day++;
    }
    for (int i = 0; i < m; i++) {
        ans[i] = (stInf[i] == -1 ? 0 : (D[i] + path[i].size() - stInf[i]));
    }
    return ans;
}
