Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
2.9 kB
1
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

#define int long long

using ll = long long;

constexpr int N = 1e5;

int n;
vector<int> g[N];
int c[N], l[N], r[N], sz[N], d[N];

ll ans = 0;

void dfs1(int u) {
    sz[u] = 1;
    for (int &v : g[u]) {
        dfs1(v);
        sz[u] += sz[v];
    }
}

bool found = true;

struct item {
    int need = 0;
    set<tuple<int, int, int>> s;
};

item a[N];

void dfs2(int u) {
    if (!found) return;
    a[u].need = -1;
    for (int &v : g[u]) {
        dfs2(v);
        if (!found) return;
        if (a[u].need == -1) {
            a[u] = a[v];
            a[v].s.clear();
            continue;
        }
        a[u].need += a[v].need;
        for (auto t : a[v].s) {
            a[u].s.insert(t);
        }
        a[v].s.clear();
    }
    a[u].need = max(a[u].need, 0LL);
    a[u].s.emplace(c[u], INT_MAX, u);
    while (a[u].need < l[u]) {
        if (a[u].s.empty()) {
            found = false;
            return;
        }
        auto [pr, cnt, who] = *(a[u].s.begin());
        int take = min(l[u] - a[u].need, cnt);
        ans += 1LL * take * pr;
        d[who] += take;
        a[u].need += take;
        if (cnt > take) {
            a[u].s.emplace(pr, cnt - take, who);
        }
        a[u].s.erase({pr, cnt, who});
    }
    if (a[u].need > r[u]) {
        found = false;
        return;
    }
    ll sum = 0;
    for (auto [pr, cnt, who] : a[u].s) {
        sum += cnt;
    }
    sum += a[u].need;
    while (sum > r[u]) {
        auto [pr, cnt, who] = *(--a[u].s.end());
        ll take = min(sum - r[u], (ll)cnt);
        sum -= take;
        if (cnt > take) {
            a[u].s.emplace(pr, cnt - take, who);
        }
        a[u].s.erase({pr, cnt, who});
    }
}

void test_case() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        p--;
        g[p].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }
    dfs1(0);
    for (int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end(), [&](int lhs, int rhs) {
            return sz[lhs] > sz[rhs];
        });
    }
    dfs2(0);
    if (!found) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
        for (int i = 0; i < n; i++) {
            cout << d[i] << ' ';
        }
        cout << '\n';
    }
    for (int i = 0; i < n; i++) {
        g[i].clear();
        d[i] = 0;
        a[i].need = 0;
        a[i].s.clear();
        found = true;
        ans = 0;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}
Leave a Comment