#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;

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;
}

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);
    for (int i = 0; i < m; i++) is[i] = I[i];
    set <ll> t_s;
    vector <array <int, 4>> when;
    for (int i = 0; i < m; i++) {
        int a = S[i], b = T[i];
        int l = lca(a, b);
        int x = D[i], y = D[i] + dist(a, l), z = D[i] + dist(a, b);
        when.pb({x, y, z, l});
        t_s.insert(x);
        t_s.insert(y);
        t_s.insert(z);
    }
    vector <int> t(all(t_s));
    vector <ll> res(m, 0);
    for (int i = 0; i < m; i++) {
        if (is[i]) res[i] = when[i][0];
    }
    int sz = t.size();
    for (int z = 0; z < sz; z++) {
        ll tm = t[z];
        vector <int> v(n+1, 0);
        for (int i= 0; i < m; i++) {
            if (when[i][2] < tm || when[i][0] > tm) continue;
            if (is[i]) {
                int k = tm - when[i][0];
                int u;
                int a = S[i], b = T[i];
                if (k == when[i][1]) u = when[i][3];
                else if (k < when[i][1]) {
                    u = go(a, k);
                }
                else {
                    u = go(b, when[i][2] - when[i][0] - k);
                }
                v[u] = 1;
            }
        }
        for (int i = 0; i < m; i++) {
            if (when[i][2] < tm || when[i][0] > tm) continue;
            if (is[i]) continue;
            int k = tm - when[i][0];
            int u;
            int a = S[i], b = T[i];
            if (tm == when[i][1]) u = when[i][3];
            else if (tm < when[i][1]) {
                u = go(a, k);
            }
            else {
                u = go(b, when[i][2] - when[i][0] - k);
            }
            if (v[u]) {
                is[i] = 1;
                res[i] = tm;
            }
        }
    }
    vector <int> ans;
    for (int i = 0; i < m; i++) {
        if (!is[i]) ans.pb(0);
        else ans.pb(when[i][2] - res[i]+1);
    }


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

    return ans;
}
/*

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

*/
