CF1098A

FiraCode · 2024-01-12 19:56:05 · 题解

思路：

考虑贪心，对于一个深度为偶数的点，那么显然将它取到它子树中每个数的权值最小。

比如这组数据：

5
1 2 2 3
1 -1 2 3 -1

考虑在 2 处设 a_2 = 1，这样可以使得 a_3 和 a_4 同时减一。

Code：

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
int s[100010];
vector<int> e[100010];
int sum;

void dfs(int u, int sfa, int fa = -1) {
    if (s[u] != -1) {
        if (s[u] < sfa) {
            puts("-1");
            exit(0);
        }
        sum += s[u] - sfa;
        for (auto v : e[u]) {
            if (v != fa)
                dfs(v, s[u], u);
        }
    } else {
        int minn = 1 << 30;
        for (auto v : e[u]) {
            if (v != fa)
                minn = min(minn, s[v] - sfa);
        }
        if (minn < 0) {
            puts("-1");
            exit(0);
        }
        if (minn != 1 << 30)
            sum += minn;
        for (auto v : e[u])
            if (v != fa)
                dfs(v, sfa + minn, u);
    }
}

signed main() {
    scanf("%lld", &n);
    for (int i = 2; i <= n; ++i) {
        int fa;
        scanf("%lld", &fa);
        e[fa].push_back(i);
        e[i].push_back(fa);
    }
    for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]);

    dfs(1, 0);

    printf("%lld\n", sum);

    return 0;
}