P5521 [yLOI2019] 梅深不见冬
（这题的暴力太难写了QAQ）
思路：看完题目很容易发现，在某点放一朵梅花本质上就是用 DFS 的方式遍历该点的子树。
那么我们只要找到在该点的子节点上放梅花的最小花费就可以了。
本题的特殊样例已经在一定程度上提醒了我们正解的思路。
首先观察特殊样例：节点 i 最多只有两个儿子 u,v 时，可以分开枚举先走 u 和先走 v 的两种情况。
设 $ans_i$ 表示节点 i 的答案，那么不难得到：
若节点 i 为叶子结点，则 $ans_i = w_i$。
否则 $ans_i = \min(ans_u + \max(ans_v - ans_u + w_u , 0) , ans_v + \max(ans_u - ans_v + w_v , 0))$
感性地理解一下：先走 u 时，首先要准备 $ans_u$ 朵梅花，在 u 结点放完梅花后，取走它子节点上的 $ans_u - w_u$ 朵梅花。
然后走 v 时，若满足 $ans_u - w_u \le ans_v$，则答案要加上 $ans_v - ans_u + w_u$。
否则若 $ans_u - w_u \gt ans_v$，则答案为 $ans_u$。
先走 v 时同理。
从刚刚的思考里不难发现：u,v 两个节点中，走 $ans_k - w_k (k \in \{u,v\})$ 较大的节点一定更优。
考虑拓展到一般情况，若点 i 有 m 个子节点 $son_1,son_2 \cdots son_m$ ，如何排列。
根据刚刚的思考和生活经验，考虑贪心：按 $ans_k - w_k (k \in \{son_1,son_2 \cdots son_m \})$ 降序排序，再按上述方法统计。
证明（参考官方题解）：
微扰。对于子节点 u,v ，设 $a_u = ans_u - w_u \gt a_v = ans_v - w_v$。
先走 u 时，答案为 $S = max(ans_u , ans_v + w_u)$。
先走 v 时，答案为 $T = max(ans_v , ans_u + w_u)$。
$\because a_u = ans_u - w_u,a_v = ans_v - w_v$
$\therefore S = max(a_u + w_u , ans_v + w_u) = w_u + max(a_u , ans_v),$
$T = max(a_v + w_v , ans_u + w_v) = w_v + max(a_v , ans_u) = w_v + w_u + a_u$。
若 $a_u \gt ans_v$，则 $S = w_u + a_u \lt w_u + a_u + w_v = T$。
若 $a_u \le ans_v$，则 $S = w_u + a_v + w_v \lt w_u + a_u + w_v = T$。
故 $S$ 恒小于 $T$，由数学归纳可得，按 $ans - w$ 降序排序必定最优。
证毕。
那么我们只需要写一个 DFS，在叶子结点直接统计答案，其余结点按上述方法统计即可。
代码如下：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 const int maxn = 1e5 + 10;
7 int n,w[maxn];
8 struct node {
9 int id,val,ans;
10 node() {
11 id = val = ans = 0;
12 }
13 node(int id,int val,int ans):id(id),val(val),ans(ans){}
14 bool operator < (const node& p)const {
15 return ans - val > p.ans - p.val;
16 }
17 }a[maxn];
18 bool cmp(int p,int q) {
19 return a[p] < a[q];
20 }
21 vector<int> son[maxn];
22 namespace work {
23 int ans[maxn],b[maxn],f[maxn];
24 void dfs(int u) {
25 if(son[u].empty()) {
26 a[u].ans = w[u];
27 return ;
28 }
29 for(int i = 0;i < son[u].size();++ i) {
30 int v = son[u][i];
31 dfs(v);
32 }
33 sort(son[u].begin() , son[u].end() , cmp);
34 int cnt = 0,ret = 0;
35 for(int i = 0;i < son[u].size();++ i) {
36 int v = son[u][i];
37 if(a[v].ans <= ret) {
38 ret -= a[v].ans;
39 }
40 else {
41 cnt += a[v].ans - ret;
42 ret = 0;
43 }
44 ret += a[v].ans - a[v].val;
45 }
46 if(w[u] <= ret)a[u].ans = cnt;
47 else a[u].ans = cnt + w[u] - ret;
48 return ;
49 }
50 int main() {
51 scanf("%d",&n);
52 for(int i = 2;i <= n;++ i) {
53 int x;
54 scanf("%d",&x);
55 son[x].push_back(i);
56 }
57 for(int i = 1;i <= n;++ i)scanf("%d",&w[i]),a[i] = node(i , w[i] , 0x3f3f3f3f);
58 dfs(1);
59 for(int i = 1;i <= n;++ i) {
60 printf("%d ",a[i].ans);
61 }
62 return 0;
63 }
64 }
65 int main() {
66 work::main();
67 return 0;
68 }
QAQ