#include "infection.h"
#include <bits/stdc++.h>
using namespace std;

/**const int MAXN = 1.5e5 + 10;
long long from[MAXN], to[MAXN], day[MAXN], infected[MAXN], direction[MAXN], s[MAXN];
long long t[MAXN], n;

const long long INFTY = 1e18;

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
) {
    n = I.size();
    
    for (int i = 0; i < n; i++) {
        from[i + 1] = S[i];
        to[i + 1] = T[i];
        day[i + 1] = D[i];
        infected[i + 1] = I[i];
    }

    for (int i = 1; i <= n; i++) {
        direction[i] = (from[i] < to[i]) ? 1 : -1;
        s[i] = from[i] - day[i] * direction[i];
        t[i] = INFTY;
    }

    priority_queue <pair <long long, int>> pq;

    for (int i = 1; i <= n; i++) {
        if (infected[i]) pq.push({0, i});
    }

    while (pq.size()) {
        auto [tt, u] = pq.top();
        pq.pop();

        if (t[u] != INFTY) continue;
        
    }

}*/

const int MAXN = 1.5e5 + 10;
vector <int> edges[MAXN];

vector <int> get_path(int u, int v, int goal) {
    if (v == goal) return {v};

    for (int x : edges[v]) {
        if (x == u) continue;
        vector <int> path = get_path(v, x, goal);
        
        if (path.size()) {
            path.push_back(v);
            if (u == v) reverse(path.begin(), path.end());

            return path;
        }
    }

    return {};
}

map <long long, vector <int>> v[MAXN];
map <long long, vector <vector <int>>> components;
long long t[MAXN], len[MAXN];

const long long INFTY = 1e18;

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;
    int m = I.size();

    for (int i = 0; i < n - 1; i++) {
        edges[R[i].first].push_back(R[i].second);
        edges[R[i].second].push_back(R[i].first);
    }

    for (int i = 0; i < m; i++) {
        t[i] = INFTY;
        if (I[i]) t[i] = D[i];

        auto path = get_path(S[i], S[i], T[i]);
        len[i] = path.size();

        for (int j = 0; j < path.size(); j++) {
            v[path[j]][D[i] + j].push_back(i);
            //cout << "PATH " << i << ' ' << path[j] << ' ' << D[i] + j << '\n';
        }
    }

    for (int i = 0; i < n; i++) {
        for (auto [day, component] : v[i]) {
            components[day].push_back(component);
        }
    }

    for (auto [day, c] : components) {
        for (auto component : c) {
            long long mn = INFTY;

            for (auto x : component) {
                mn = min(mn, t[x]);
            }

            if (mn > day) continue;

            for (auto x : component) {
                if (t[x] > day) t[x] = day;
            }
        }
    }

    vector <int> ans;

    for (int i = 0; i < m; i++) {
        if (D[i] + len[i] - t[i] < 0) assert(t[i] == INFTY);
        long long c = max(0LL, (long long) D[i] + len[i] - t[i]);
        ans.push_back(c);
    }

    return ans;
}