梅深不见冬 题解

题面

原题：P5521 [yLOI2019] 梅深不见冬

样例：

6
1 1 2 3 4
3 14 1 5 12 15

输出：

21 20 13 20 12 15

题解

这个题类似于国王游戏，要考虑每个节点的贡献。
对于一个节点 x，设ans_x表示要在x节点上放梅花至少需要准备ans_x朵梅花，而x的权值为w_x，我们的问题是要选出一个最优的序列，使得最终需要准备的梅花最少。这个问题的答案是按照ans_x - w_x不升序排列即可。我们可以类比国王游戏，考虑两个节点先后顺序对整体答案的影响，进而推广到整棵树。
尝试证明这个结论：
我们考虑两个节点i,j，设a_i = ans_i - w_i,a_j = ans_j - w_j且a_i > a_j。
假设先放i再放j，那么我们需要准备的梅花数为max(ans_i,w_i + ans_j)（一式），同理，先放j再放i需要准备的梅花数为max(ans_j,w_j+ans_i)（二式）。
由于a_i = ans_i - w_i，得ans_i=a_i+w_i。ans_j同理。对一式二式分别提出w。
则

若一式的max取a_i，那么

若一式的max取ans_j，那么

因此一式恒小于二式，先放i更优。
由此做数学归纳可得，按照ans-w的不升序排列后的序列最优。发现上述结论可以用于树上的每个节点，复杂度O(nlogn)，注意特判没有子节点的情况，ans_i=w_i。

代码

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<vector>  
using namespace std;  
  
const int N = 1e5 + 10;  
  
int n, ans[N], w[N];  
vector<int> e[N];  
bool cmp(int x, int y){  
    return ans[x] - w[x] > ans[y] - w[y];  
}  
  
void dfs(int u){  
	//记录最少需要多少梅花，也就是w_u + 所有(w_son)
    int sum = 0;  
    for(auto to : e[u]){  
        dfs(to);  
        sum += w[to];  
    }  
    //特判没有子节点的情况
    if(e[u].empty()) ans[u] = w[u];  
    else {  
        sum += w[u];  
	    //按照ans-w不升序排列
        sort(e[u].begin(), e[u].end(), cmp); 
        //now记录当前至少需要多少梅花 
        int now = 0;  
        for(auto v : e[u]){  
            ans[u] = max(ans[u], now + ans[v]);  
            now += w[v];  
        }  
        ans[u] = max(ans[u], sum);  
    }  
}  
int main(){  
    scanf("%d", &n);  
    for(int i = 1; i < n; i++){  
        int x; scanf("%d", &x);  
        e[x].push_back(i + 1);  
    }  
    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;  
}