#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5009;

bool e[N], bad[N];
vector < int > crr, g[N], vec[N];
ll n, m, d[N], fr[N], to[N], res[N], pt[N];

bool path(int v, int p, int fin) {
    crr.push_back(v);
    if (v == fin) return 1;
    for (auto u : g[v]) if (u != p && path(u, v, fin)) return 1;
    crr.pop_back();
    return 0;
}

vector < int > solve(vector<pair<int,int>> ed, vector<ll> dd, vector<int> ss, vector<int> tt, vector<bool> ee) {
    m = (int)dd.size();
    n = (int)ed.size() + 1;

    for (int i = 1; i <= m; i++) {
        fr[i] = ss[i - 1] + 1, to[i] = tt[i - 1] + 1;
        e[i] = ee[i - 1], d[i] = dd[i - 1];
        if (e[i]) res[i] = d[i]; else res[i] = -1;
    }

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

    vector < array < ll , 3 > > op;

    for (int i = 1; i <= m; i++) {
        crr.clear();
        path(fr[i], fr[i], to[i]);
        vec[i] = crr;
        op.push_back({d[i], i, 1});
        op.push_back({d[i] + (int)crr.size(), i, -1});
        pt[i] = 0;
    }

    ll tm = 0;
    int j = 0;
    vector < int > act;
    sort(op.begin(), op.end());

    while (true) {
        if (act.empty() || op[j][0] <= tm) {
            if (j >= (int)op.size()) break;
            int l = j;
            while (l < (int)op.size() && op[l][0] == op[j][0]) {
                array < ll , 3 > pr = op[l];
                if (pr[2] == 1) act.push_back(pr[1]);
                else {
                    for (int i = 0; i < (int)act.size(); i++) if (act[i] == pr[1]) {
                        swap(act[i], act.back());
                        act.pop_back();
                        break;
                    }
                }
                l++;
            }
            tm = op[j][0];
            j = l;
        }

        for (int i : act) if (e[i]) bad[vec[i][pt[i]]] = 1;
        for (int i : act) if (!e[i] && bad[vec[i][pt[i]]]) {
            e[i] = 1;
            res[i] = tm;
        }
        for (int i : act) bad[vec[i][pt[i]]] = 0;

        tm++;
        for (int i : act) pt[i]++;
    }

    vector < int > ans(m);
    for (int i = 1; i <= m; i++) ans[i - 1] = (res[i] < 0 ? 0 : d[i] + (ll)vec[i].size() - res[i]);
    return ans;
}