#include "infection.h"
#include <vector>
#include <utility>

#include <bits/stdc++.h>

using namespace std;

//#include "grader.cpp"

//#define nl '\n'
#define nl endl

using ll = long long;

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
) {
    int n = R.size() + 1;

    vector<vector<int>> adj(n);

    for(int i = 0; i < n - 1; i++) {
        int u = R[i].first, v = R[i].second;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<int>> jmp(n, vector<int>(20));

    vector<int> par(n), tin(n), tout(n), d(n);

    int timer = 0;

    auto dfs = [&](auto &&self, int v, int p) -> void {
        par[v] = p;

        jmp[v][0] = p;

        for(int i = 1; i < 20; i++) {
            jmp[v][i] = jmp[ jmp[v][i - 1] ][i - 1];
        }

        tin[v] = ++timer;

        for(auto to : adj[v]) {
            if(to == p) continue;

            d[to] = d[v] + 1;

            self(self, to, v);
        }

        tout[v] = timer;
    };

    dfs(dfs, 0, 0);

    auto upper = [&](int u, int v) {
        return tin[v] >= tin[u] && tout[v] <= tout[u];
    };

    auto lca = [&](int u, int v) {
        if(upper(u, v)) return u;

        for(int i = 19; i >= 0; i--) {
            if(!upper(jmp[u][i], v)) u = jmp[u][i];
        }

        return jmp[u][0];
    };

    auto dist = [&](int u, int v) {
        return d[u] + d[v] - 2 * d[lca(u, v)];
    };

    vector<vector<int>> where(n, vector<int>(n));

    for(int i = 0; i < n; i++) {
        int u = par[i], prev = i;

        while(prev != 0) {
            where[u][i] = prev;
            prev = u;
            u = par[u];
        }
    }

    auto next = [&](int u, int v) {
        if(u == v) return -1;
        if(!upper(u, v)) return par[u];
        return where[u][v];
    };

    int m = D.size();

    vector<vector<int>> place(m, vector<int>(n, -1));

    for(int i = 0; i < m; i++) {
        int u = S[i], j = 0;

        while(u != -1) {
            place[i][j] = u;
            u = next(u, T[i]);
            j++;
        }
    }

    set<int> act, neact;

    vector<ll> when(m, (ll)1e18);

    for(int i = 0; i < m; i++) {
        if(I[i]) {
            act.emplace(i);
            when[i] = 0;
        } else {
            neact.emplace(i);
        }
    }

    auto in_when = [&](int i, int j) -> ll {
        int u = place[i][when[i]];
        ll du = D[i] + when[i];

        int v = S[j];
        ll dv = D[j];

        ll resu = when[i], resv = 0;

        if(du > dv) {
            if(du - dv >= n) return -1;
            if(place[j][du - dv] == -1) return -1;
            v = place[j][du - dv];
            resv += du - dv;
        }

        if(dv > du) {
            if(resu + dv - du >= n) return -1;
            if(place[i][resu + dv - du] == -1) return -1;
            u = place[i][resu + dv - du];
            resu += dv - du;
        }

        ll dst = dist(u, v);

//        if(i == 2 && j == 3) {
//            cout << "wheni: " << when[i] << nl;
//            cout << "du dv: " << du << ' ' << dv << nl;
//            cout << "u v: " << u << ' ' << v << nl;
//            cout << "dst: " << dst << nl;
//        }

        if(dst & 1) return -1;

        dst /= 2;

        if(resu + dst >= n || place[i][resu + dst] == -1) return -1;
        if(resv + dst >= n || place[j][resv + dst] == -1) return -1;

        return resv + dst;
    };

    while(!act.empty()) {
        set<int> nact, nneact;

        for(auto i : act) {
            for(auto j : neact) {
                int val = in_when(i, j);

//                if(i == 2 && j == 3) {
//                    cout << val << nl;
//                }

                if(val != -1 && when[j] > val) {
                    when[j] = val;
                }
            }
        }

        for(auto j : neact) {
            if(when[j] == (ll)1e18) {
                nneact.emplace(j);
            } else {
                nact.emplace(j);
            }
        }

        swap(nact, act);
        swap(neact, nneact);
    }

    vector<int> ans(m);

    for(int i = 0; i < m; i++) {
        if(when[i] != (ll)1e18) {
            ans[i] = dist(place[i][when[i]], T[i]) + 1;
        }
    }

    return ans;
}

/**

9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
1 0 5 1
3 5 7 0
4 5 7 0
8 7 8 0
10 0 1 0


**/
