[yLOI2019] 梅深不见冬

题目背景

风，吹起梅岭的深冬；霜，如惊涛一样汹涌；
雪，飘落后把所有烧成空，像这场，捕捉不到的梦。
醒来时已是多年之久，宫门铜环才长了铁锈，也开始生出离愁。

——银临《梅深不见冬》

题目描述

扶苏从深冬的梅岭走出，来到了一棵有 $n$ 个节点的有根树上。

如果你不知道什么是树，可以认为树是一个边数恰好比节点个数少一的简单无向连通图。

如果我们规定 $x$ 是树 $T$ 的根，那么定义任意一个节点 $y$ 到根的路径就是从 $y$ 出发不重复经过节点到达 $x$ 所经过的所经过的点构成的点集。可以证明这样的点集有且仅有一个。

定义一个节点 $u$ 是节点 $v$ 的孩子，当且仅当 $u$ 与 $v$ 相连且 $u$ 不在 $v$ 到根的路径中。如果 $u$ 是 $v$ 的孩子，那么定义 $v$ 是 $u$ 的家长节点。

如果我是 @\_rqy 那种毒瘤神仙的话，可能会问你每个节点的孩子数不超过 $k$ 的 $n$ 个节点的带标号无根树一共有多少个，可惜这个问题我也不会，所以我不会问你这么毒瘤的问题。

扶苏从这棵 $n$ 个节点的树的 $1$ 号节点出发，沿着树上的边行走。当然我们规定 $1$ 号节点是这棵树的根。他所行走的规定是：当扶苏在节点 $u$ 时，扶苏要么在 $u$ 的孩子中选择一个没有到达过的节点 $v$ 并行走到 $v$，要么选择回到 $u$ 的家长节点。

现在给每个节点一个权值 $w$，其中 $i$ 号节点的权值为 $w_i$。他想给这棵树的某个节点放上从梅岭带出的梅花。我们规定扶苏能在节点 $u$ 放上梅花当且仅当满足如下条件：

扶苏当前在节点 $u$。

对于 $u$ 的所有孩子 $v$，节点 $v$ 被放上了 $w_v$ 朵梅花。

同时，扶苏可以在任意时刻收回任意节点上的梅花，在收回梅花时不需要走到对应节点。

现在扶苏想问问你，对于每个节点，如果他想在 $i$ 号节点上放 $w_i$ 朵梅花，那么他最少要从梅岭带出多少朵梅花。

输入格式

每个输入文件中都有且仅有一组测试数据。

数据的第一行是一个整数 $n$ 代表树的节点个数。

第二行有 $n-1$ 个用空格隔开的整数，第 $i$ 个整数 $p_i$ 代表第 $i+1$ 号节点的家长节点编号。

第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $w_i$。

输出格式

输出一行 $n$ 个用空格隔开的整数，第 $i$ 个整数代表想在 $i$ 号节点上放 $w_i$ 朵梅花需要准备的梅花个数。

样例 #1

样例输入 #1

3 
1 2 
1 1 1

样例输出 #1

2 2 1

样例 #2

样例输入 #2

3
1 1
1 1 1

样例输出 #2

3 1 1

样例 #3

样例输入 #3

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

样例输出 #3

21 20 13 20 12 15

提示

输入输出样例 1 解释

样例 1 的输入如上图，每个节点都需要放 $1$ 一朵梅花。

如果在 1 号节点放梅花，则从一号点运动到 2 号点，然后运动到 3 号点，在 3 号点上放一朵梅花，返回 2 号点，在 2 号点上放一朵梅花，同时收回三号点的梅花，然后返回 1 号点，将从 3 号点收回的梅花放到 1 号点即可。一共需要两朵梅花。

在 2、3 号节点放梅花的方案类似。

输入输出样例 3 解释

样例 3 的输入如左图。

先从 1 号节点运动至 3 号节点，再运动至 5 号节点，在 5 号节点上放置 $12$ 朵梅花，然后返回 3 号节点，在 3 号节点上放置 $1$ 朵梅花，收回五号节点的 $12$ 朵梅花，返回 1 号节点。

然后运动到 2 号节点，通过 4 号节点运动到 6 号节点，放下 $15$ 朵梅花，返回 4 号节点放下 $5$ 朵梅花，此时树上有的梅花数为 $5 + 15 + 1 = 21$，分别在 4 号、6 号和 3 号节点上。然后收回 6 号节点的梅花，返回 2 号节点，放下 $14$ 朵梅花，收回 4 号节点的，返回 1 号节点，在 1 号节点上放置 $3$ 朵梅花，即可达到在 1 号节点上放梅花的目的。

可以验证最大花费为 $21$。其他节点的答案同理。

请注意，其他节点的答案不一定是按照该节点的运动路径行走得到的。

数据规模与约定

• 对于测试点 5、6，满足特殊性质：每个节点的孩子结点个数不超过 $2$。
• 对于测试点 8 到测试点 10，满足特殊性质：每个节点的孩子节点个数不超过 $5$。
• 对于测试点 11 到测试点 14，满足特殊性质：任意一个节点到根的路径上的点数不超过 $3$，也即树高不超过 $3$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5 + 4,~1 \leq p_i \leq i,~1 \leq w_i \leq 1000$。

提示

• $n$ 的末位数字可以帮助你快速的判断测试点所具有的的特殊性质。

题解

题意简述：

一颗有权有根树，你可以遍历整棵树最多一次，在节点 $u$ 时，如果其所有儿子都被点亮，就可以在节点 $u$ 放下梅花。你可以在任意时刻收回任意节点的梅花。规定一个节点被点亮当且仅当梅花数量到达该点点权 $w_i$ 。求对于每个节点 $i$ ，如果我要在这一次遍历中点亮节点 $i$ ，至少要从起点携带的梅花的数目、

观察数据范围节点个数为$10^5$，要求输出每个节点的答案，考虑DP转移。

我们容易发现，最少要从梅岭带出多少朵梅花其实就是遍历树的所有时刻所用的梅花的最大值，即梅花数量峰值。记节点 $i$ 及其子树内使用梅花的峰值数量为 $h_i$ 。

我们还发现，这个峰值是和遍历儿子的顺序有关系的。遍历节点 $u$ 的儿子的时候，前面遍历过的儿子一直要保留 $w_v$ 的梅花，其会对 $h_u$ 造成影响。所以我们要找到一种遍历顺序，使得这个峰值最小。

对于节点 $u$ ，有如下式子成立：

$$ h_u = max_{v\in T_u}\{h_v+\sum_{x\in Pre_v}w_x\} $$

我们发现子树内的贡献是不受子树外影响的，所以我们可以以任意顺序先求出每个儿子的答案，再考虑该节点的答案。于是上式可抽象为下问题：

有 $n$ 个元素，第 $i$ 个元素有 $a_i$，$b_i$ 两个属性，要求排列这 $n$ 个元素使得最小化

$$ S = max_{i=1}^{n}\{a_i+\sum_{j=1}^{i-1}b_j\} $$

这个式子考虑采用微扰法，用邻项交换解决。
上图。

只考虑 $i$ 和 $i+1$ 这个局部的贡献。

记式中 $\sum_{j=1}^{i-1}b_j$ 为 $S$ 。
那么现在的贡献为 $max\{S+a_i,S+b_i+a_{i+1}\}$
如果交换一下这相邻的两项呢？

贡献变为 $max\{S+a_{i+1},S+b_{i+1}+a_{i}\}$

直接sort即可。
当然也能推式子。

如果想要原式的贡献更小，即要求 $max\{S+a_i,S+b_i+a_{i+1}\} < \max\{S+a_{i+1},S+b_{i+1}+a_{i}\}$
显然有 $S+b_{i+1}+a_{i}>S+a_i$，$S+b_i+a_{i+1}>S+a_{i+1}$
所以上不等式等价于$S+b_i+a_{i+1} < S+b_{i+1}+a_{i}$
即$b_i+a_{i+1} < b_{i+1}+a_{i}$时，原序更优。

所以每次遍历完儿子后，按照这个排序一遍再求贡献，即可求出该节点答案。

结合代码理解：

const int N = 1e5+10;
int n,m;
int h[N],w[N];
vector<int> T[N];
bool cmp(int i,int j){
    return h[j] + w[i] < h[i] + w[j];
}
void dfs(int u){
    for(auto v:T[u]){
        dfs(v);
    }
    if(!T[u].size()){//leaf
        h[u] = w[u];
        return ;
    }
    sort(T[u].begin(),T[u].end(),cmp);
    int pre = 0;
    int mx = 0;
    for(auto i:T[u]){
        mx = max(mx,h[i]+pre);
        pre += w[i];
    }
    h[u] = max(mx,pre+w[u]);
}
void solve(){
    cin>>n;
    for(int i=2,f;i<=n;i++){
        cin>>f;
        T[f].push_back(i);
    }
    for(int i=1;i<=n;i++)cin>>w[i];
    dfs(1);
    for(int i=1;i<=n;i++){
        cout<<h[i]<<' ';
    }
}