#include <bits/stdc++.h>

using namespace std;

const int logN = 18;

struct Event {
    long long t;
    int ind, v;
};

vector<int> solve(vector<pair<int, int>> edges, vector<long long> d, vector<int> s, vector<int> t, vector<bool> infected) {
    int n = edges.size() + 1, m = d.size();

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

    vector<int> tin(n), tout(n), depth(n);
    vector<vector<int>> up(logN, vector<int>(n, -1));
    int timer = 0;

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

        for (int &u : tree[v]) {
            if (u != up[0][v]) {
                up[0][u] = v;
                depth[u] = depth[v] + 1;
                dfs(u);
            }
        }

        tout[v] = timer;
    };

    dfs(0);

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

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

        if (isAnc(v, u))
            return v;

        for (int i = logN - 1; i >= 0; i--) {
            if (up[i][u] != -1 && !isAnc(up[i][u], v))
                u = up[i][u];
        }

        return up[0][u];
    };

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

    auto path = [&](int u, int v) {
        vector<int> res;

        while (!isAnc(u, v)) {
            res.push_back(u);
            u = up[0][u];
        }

        res.push_back(u);

        vector<int> part2;

        while (u != v) {
            part2.push_back(v);
            v = up[0][v];
        }

        reverse(part2.begin(), part2.end());

        for (int &val : part2)
            res.push_back(val);

        return res;
    };

    if (n <= 5000 && m <= 5000) {
        vector<Event> events;

        for (int i = 0; i < m; i++) {
            long long curr = d[i];
            for (int val : path(s[i], t[i]))
                events.push_back({curr++, i, val});
        }

        int evs = events.size();

        sort(events.begin(), events.end(), [](auto x, auto y) {
             if (x.t == y.t)
                return x.v < y.v;
             return x.t < y.t;
        });

        vector<int> ans(m);

        auto Equal = [&](auto x, auto y) {
            return x.t == y.t && x.v == y.v;
        };

        for (int i = 0; i < evs; i++) {
            bool flag = infected[events[i].ind];

            int j = i + 1;
            while (j < evs && Equal(events[i], events[j])) {
                flag |= (infected[events[j].ind]);
                j++;
            }

            if (flag) {
                while (i < j) {
                    infected[events[i].ind] = true;
                    ans[events[i].ind]++;
                    i++;
                }
            }

            i = j - 1;
        }

        return ans;

    }

    vector<vector<int>> st(n);
    for (int i = 0; i < m; i++)
        st[s[i]].push_back(i);

    for (int i = 0; i < m; i++) {
        bool flag = false;

        for (int &ind : st[i])
            flag |= infected[ind];

        if (flag) {
            for (int &ind : st[i])
                infected[ind] = true;
        }
    }

    vector<int> ans(m);
    for (int i = 0; i < m; i++)
        ans[i] = (t[i] - s[i] + 1) * infected[i];

    return ans;
}