P5521 [yLOI2019] 梅深不见冬

看题目可以发现每个点的需求需要看它儿子所需要的值，所以就可以理所当然的想到将所有的点的儿子节点加在一起，然后排序，让大的先处理，所以我们就得到了一分美好的代码。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 9;
int n;
vector <int> V[N];
int fa[N], w[N];
int sum[N], ans[N];
struct node {
    int sub;
    bool operator<(const node &tmp) const {
        return sum[sub] < sum[tmp.sub];
    }
};
int dfs(int sx) {
    if (ans[sx] != 0) return ans[sx];
    if (V[sx].size() == 0) return ans[sx] = w[sx];
    priority_queue<node> q;
    while (!q.empty()) q.pop();
    for (int i : V[sx]) q.emplace((node){i});
    int s = 0, tmp;
    while (!q.empty()) {
        int v = q.top().sub;
        q.pop();
        tmp = dfs(v);
        if (tmp + s > ans[sx])
            ans[sx] = tmp + s;
        s += w[v];
    }
    if (s + w[sx] > ans[sx])
        ans[sx] = s + w[sx];
    return ans[sx];
}
int main() {
    scanf ("%d", &n);
    for (int i = 2;i <= n; ++ i) {
        scanf ("%d", fa + i);
        V[fa[i]].push_back(i);
    }
    for (int i = 1;i <= n; ++ i) scanf ("%d", w + i);
    for (int i = 1;i <= n; ++ i)
        for (int j : V[i])
            sum[i] += w[j];
    dfs (1);
    for (int i = 1;i <= n; ++ i)
        printf ("%d ", ans[i]);
    return 0;
}

它不负众望的 WA 掉了。

我们回头再仔细思考，每一个点所需要的真的就只是它儿子的和吗？

其实不然，实际上不会影响后面的是 $ans_i-w_i$，所以我们只要将排序的标准换一下就能得到正确答案了。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 9;
int n;
vector <int> V[N];
int fa[N], w[N];
int sum[N], ans[N];
struct node {
    int sub;
    bool operator<(const node &tmp) const {
        return ans[sub] - w[sub] < ans[tmp.sub] - w[tmp.sub];
    }
};
void dfs(int sx) {
    if (V[sx].size() == 0) {
        ans[sx] = w[sx];
        return ;
    }
    priority_queue<node> q;
    while (!q.empty()) q.pop();
    for (int i : V[sx]){
        dfs (i);
        q.emplace((node){i});
    }
    int s = 0;
    while (!q.empty()) {
        int v = q.top().sub;
        q.pop();
        if (ans[v] + s > ans[sx])
            ans[sx] = ans[v] + s;
        s += w[v];
    }
    if (s + w[sx] > ans[sx])
        ans[sx] = s + w[sx];
    return ;
}
int main() {
    scanf ("%d", &n);
    for (int i = 2;i <= n; ++ i) {
        scanf ("%d", fa + i);
        V[fa[i]].push_back(i);
    }
    for (int i = 1;i <= n; ++ i) scanf ("%d", w + i);
    dfs (1);
    for (int i = 1;i <= n; ++ i)
        printf ("%d ", ans[i]);
    return 0;
}