#include "infection.h"
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;

vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {
    int n = R.size() + 1, m = D.size();

    vector<vector<int>> g(n);
    for (auto& [u, v]: R) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bool sub4 = 1;
    for (int i = 1; i < (int)D.size(); ++i) {
        sub4 = (D[i] - D[i - 1] < (long long)1e6 ? 0 : sub4);
    }

    if (n <= 5000) {
        int timer = 1;
        vector<int> depth(n);
        vector<int> tin(n), tout(n);
        vector<vector<int>> up(n, vector<int>(15));

        function<void(int, int)> dfs = [&](int v, int p) {
            tin[v] = timer++;
            depth[v] = depth[p] + 1;

            up[v][0] = p;
            for (int i = 1; i < 15; ++i) {
                up[v][i] = up[up[v][i - 1]][i - 1];
            }

            for (auto& u: g[v]) {
                if (u == p) continue;
                dfs(u, v);
            }

            tout[v] = timer++;
        };

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

        auto lca = [&](int a, int b) {
            if (upper(a, b)) return a;
            if (upper(b, a)) return b;

            for (int i = 14; i >= 0; --i) {
                if (!upper(up[a][i], b)) {
                    a = up[a][i];
                }
            }

            return up[a][0];
        };

        dfs(0, 0);

        vector<long long> mn(m, inf);
        vector<array<long long, 3>> in;
        for (int i = 0; i < m; ++i) {
            if (I[i]) mn[i] = D[i];

            int l = lca(S[i], T[i]);
            if (l == S[i] || l == T[i]) {
                if (l == T[i]) {
                    int ptr = S[i];
                    long long time = D[i];
                    while (1) {
                        in.push_back({time++, ptr, i});
                        if (ptr == l) break;
                        ptr = up[ptr][0];
                    }
                } else {
                    int ptr = T[i];
                    long long time = D[i] - 2 * depth[l] + depth[S[i]] + depth[T[i]];
                    while (1) {
                        in.push_back({time--, ptr, i});
                        if (ptr == l) break;
                        ptr = up[ptr][0];
                    }
                }
            } else {
                int ptr = S[i];
                long long time = D[i];
                while (1) {
                    in.push_back({time++, ptr, i});
                    if (ptr == l) break;
                    ptr = up[ptr][0];
                }

                ptr = T[i];
                time = D[i] - 2 * depth[l] + depth[S[i]] + depth[T[i]];
                while (1) {
                    in.push_back({time--, ptr, i});
                    if (ptr == l) break;
                    ptr = up[ptr][0];
                }
            }
        }

        sort(in.begin(), in.end());

        int k = in.size();
        for (int j = 0; j < k; ++j) {
            int l = j, r = j;
            bool t = 0;

            while (r < k && in[l][0] == in[r][0] && in[l][1] == in[r][1]) {
                t |= (mn[in[r][2]] != inf), ++r;
            }
            j = r - 1;

            if (!t || r - l == 1) continue;

            while (l < r) {
                long long val = mn[in[l][2]];
                mn[in[l][2]] = min(val, in[l][0]);
                ++l;
            }
        }

        auto dist = [&](int a, int b) {
            int l = lca(a, b);
            return depth[a] + depth[b] - 2 * depth[l];
        };

        vector<int> ans;
        for (int i = 0; i < m; ++i) {
            ans.push_back(mn[i] == inf ? 0 : D[i] + dist(S[i], T[i]) - mn[i] + 1);
        }

        return ans;
    } else if (sub4) {
        int timer = 1;
        vector<int> depth(n);
        vector<int> tin(n), tout(n);
        vector<vector<int>> up(n, vector<int>(20));

        function<void(int, int)> dfs = [&](int v, int p) {
            tin[v] = timer++;
            depth[v] = depth[p] + 1;

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

            for (auto& u: g[v]) {
                if (u == p) continue;
                dfs(u, v);
            }

            tout[v] = timer++;
        };

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

        auto lca = [&](int a, int b) {
            if (upper(a, b)) return a;
            if (upper(b, a)) return b;

            for (int i = 19; i >= 0; --i) {
                if (!upper(up[a][i], b)) {
                    a = up[a][i];
                }
            }

            return up[a][0];
        };

        dfs(0, 0);

        vector<long long> mn(m, inf);
        for (int i = 0; i < m; ++i) {
            if (I[i]) mn[i] = D[i];
        }

        auto dist = [&](int a, int b) {
            int l = lca(a, b);
            return depth[a] + depth[b] - 2 * depth[l];
        };

        vector<int> ans;
        for (int i = 0; i < m; ++i) {
            ans.push_back(mn[i] == inf ? 0 : D[i] + dist(S[i], T[i]) - mn[i] + 1);
        }

        return ans;
    } else {
        int timer = 1;
        vector<int> depth(n);
        vector<int> tin(n), tout(n);
        vector<vector<int>> up(n, vector<int>(15));

        function<void(int, int)> dfs = [&](int v, int p) {
            tin[v] = timer++;
            depth[v] = depth[p] + 1;

            up[v][0] = p;
            for (int i = 1; i < 15; ++i) {
                up[v][i] = up[up[v][i - 1]][i - 1];
            }

            for (auto& u: g[v]) {
                if (u == p) continue;
                dfs(u, v);
            }

            tout[v] = timer++;
        };

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

        auto lca = [&](int a, int b) {
            if (upper(a, b)) return a;
            if (upper(b, a)) return b;

            for (int i = 14; i >= 0; --i) {
                if (!upper(up[a][i], b)) {
                    a = up[a][i];
                }
            }

            return up[a][0];
        };

        dfs(0, 0);

        vector<long long> mn(m, inf);
        vector<array<long long, 3>> in;
        for (int i = 0; i < m; ++i) {
            if (I[i]) mn[i] = D[i];

            int l = lca(S[i], T[i]);
            if (l == S[i] || l == T[i]) {
                if (l == T[i]) {
                    int ptr = S[i];
                    long long time = D[i];
                    while (1) {
                        in.push_back({time++, ptr, i});
                        if (ptr == l) break;
                        ptr = up[ptr][0];
                    }
                } else {
                    int ptr = T[i];
                    long long time = D[i] - 2 * depth[l] + depth[S[i]] + depth[T[i]];
                    while (1) {
                        in.push_back({time--, ptr, i});
                        if (ptr == l) break;
                        ptr = up[ptr][0];
                    }
                }
            } else {
                int ptr = S[i];
                long long time = D[i];
                while (1) {
                    in.push_back({time++, ptr, i});
                    if (ptr == l) break;
                    ptr = up[ptr][0];
                }

                ptr = T[i];
                time = D[i] - 2 * depth[l] + depth[S[i]] + depth[T[i]];
                while (1) {
                    in.push_back({time--, ptr, i});
                    if (ptr == l) break;
                    ptr = up[ptr][0];
                }
            }
        }

        sort(in.begin(), in.end());

        int k = in.size();
        for (int j = 0; j < k; ++j) {
            int l = j, r = j;
            bool t = 0;

            while (r < k && in[l][0] == in[r][0] && in[l][1] == in[r][1]) {
                t |= (mn[in[r][2]] != inf), ++r;
            }
            j = r - 1;

            if (!t || r - l == 1) continue;

            while (l < r) {
                long long val = mn[in[l][2]];
                mn[in[l][2]] = min(val, in[l][0]);
                ++l;
            }
        }

        auto dist = [&](int a, int b) {
            int l = lca(a, b);
            return depth[a] + depth[b] - 2 * depth[l];
        };

        vector<int> ans;
        for (int i = 0; i < m; ++i) {
            ans.push_back(mn[i] == inf ? 0 : D[i] + dist(S[i], T[i]) - mn[i] + 1);
        }

        return ans;
    }

    return {};
}
