#include "infection.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n, m;
const int K = 20, B = 200;
vector <vector <int>> g, up;
vector <int> lev, in, out;
int te=-1;
vector <map <int, vector <int>>> e;

void dfs(int u, int c=-1) {
    in[u] = ++te;
    for (int &i : g[u]) {
        if (i == c) continue;
        lev[i] = lev[u] + 1;
        up[0][i] = u;
        dfs(i, u);
    }
    out[u] = te;
}
void build() {
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= n; j++) {
            if (up[i-1][j] == -1) up[i][j] = -1;
            else {
                up[i][j] = up[i-1][up[i-1][j]];
            }
        }
    }
}
bool issub(int a, int b) {
    if (in[a] <= in[b] && out[a] >= out[b]) return 1;
    return 0;
}
int lca(int a, int b) {
    if (issub(a, b)) return a;
    if (issub(b, a)) return b;
    for (int i = K; i >= 0; i--) {
        if (up[i][a] == -1) continue;
        if (issub(up[i][a], b)) continue;
        a = up[i][a];
    }
    return up[0][a];
}
int dist(int a, int b) {
    return lev[a] + lev[b] - lev[lca(a, b)] * 2;
}
int go(int a, int b) {
    for (int i = K; i >= 0; i--) {
        if (b & (1LL << i)) {
            a = up[i][a];
        }
    }
    return a;
}

void dfs1(int u, int t, int id, int tg, int c=-1) {
    e[u][t].pb(id);
    if (u == tg) return;
    for (int &i : g[u]) {
        if (!issub(i, tg)) continue;
        dfs1(i, t+1, id, tg, u);
    }
}

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;
    g.resize(n+1);
    lev.assign(n+1, 0);
    up.assign(K+1, vector <int>(n+1, -1));
    in.assign(n+1, 0);
    out.assign(n+1, 0);
    for (int i = 0; i < n - 1; i++) R[i].ff++, R[i].ss++;
    for (int i = 0; i < S.size(); i++) S[i]++, T[i]++;
    for (int i = 0; i < R.size(); i++) {
        int a = R[i].ff, b = R[i].ss;
        g[a].pb(b);
        g[b].pb(a);
    }
    m = D.size();
    dfs(1);
    build();
    vector <bool> is(m, 0);
    vector <int> ans(m, 0);
    for (int i = 0; i < m; i++) {
        is[i] = I[i];
        if (is[i]) ans[i] = D[i];
    }

    for (int t = 0; t <= n; t++) {
        vector <int> pos(m, -1);
        for (int i = 0; i < m; i++) {
            int start = D[i], end = D[i] + dist(S[i], T[i]), l = lca(S[i], T[i]);
            int mid = dist(S[i], l);
            if (end < t) continue;
            int k = t - start;
            int u;
            int a = S[i], b = T[i];
            if (k == mid) u = l;
            else if (k < mid) {
                u = go(a, k);
            }
            else {
                u = go(b, end - start - k);
            }
            pos[i] = u;
        }
        vector <int> inf(n+1, 0);
        for (int i = 0; i < m; i++) {
            if (is[i] && pos[i] != -1) inf[pos[i]] = 1;
        }
        for (int i = 0; i < m; i++) {
            if (pos[i] != -1 && inf[pos[i]] && !is[i]) {
                is[i] = 1;
                ans[i] = t;
            }
        }
    }

    vector <int> res;
    for (int i = 0; i < m; i++) {
        if (is[i]) res.pb(D[i] + dist(S[i], T[i]) - ans[i] + 1);
        else res.pb(0);
    }

    g.clear();
    lev.clear();
    up.clear();
    in.clear();
    out.clear();
    te = -1;

    return res;
}
/*

5 3
0 1
0 2
1 3
1 4
0 3 4 0
0 1 2 0
0 4 2 1 

*/

