Sum in the tree

题解

贪心，从上向下，如果(s[u] = -1)，则(a[u]:=)以(u)为根的子树中的最小(s)减去(s[pa[u]])。否则，(a[u]:=s[u] - s[pa[u]])。

代码

void DFS1(int u, int pa) {
    for (auto v : G[u]) if (v != pa) {
        DFS1(v, u);
        Min[u] = min(Min[u], Min[v]);
    }
}

void DFS2(int u, int pa) {
    for (auto v : G[u]) if (v != pa) {
        if (Min[v] < s[u]) {
            flag = 1;
            return;
        }
        if (s[v] == -1) {
            if (Min[v] == INF32) {
                a[v] = 0;
            }
            else {
                a[v] = Min[v] - s[u];
                s[v] = Min[v];
            }
        }
        else a[v] = s[v] - s[u];
        DFS2(v, u);
    }
}

int main()
{
    cin >> n;
    Rep(i, 2, n) {
        int u;
        cin >> u;

        G[i].pb(u);
        G[u].pb(i);
    }
    Rep(i, 1, n) {
        cin >> s[i];
        Min[i] = (s[i] == -1 ? INF32 : s[i]);
    }


    DFS1(1, 0);

    if (s[1] == -1) a[1] = Min[1];
    else a[1] = s[1];

    DFS2(1, 0);

    LL res = 0;
    Rep(i, 1, n) res += a[i];

    if (flag) res = -1;

    cout << res << endl;
    return 0;
}