#P5521. [yLOI2019] 梅深不见冬

    ID: 4720 远端评测题 1000ms 500MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>贪心2019O2优化排序深度优先搜索,DFS

[yLOI2019] 梅深不见冬

题目背景

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

——银临《梅深不见冬》

题目描述

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

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

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

定义一个节点 uu 是节点 vv 的孩子,当且仅当 uuvv 相连且 uu 不在 vv 到根的路径中。如果 uuvv 的孩子,那么定义 vvuu 的家长节点。

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

扶苏从这棵 nn 个节点的树的 11 号节点出发,沿着树上的边行走。当然我们规定 11 号节点是这棵树的根。他所行走的规定是:当扶苏在节点 uu 时,扶苏要么在 uu 的孩子中选择一个没有到达过的节点 vv 并行走到 vv,要么选择回到 uu 的家长节点。

现在给每个节点一个权值 ww,其中 ii 号节点的权值为 wiw_i。他想给这棵树的某个节点放上从梅岭带出的梅花。我们规定扶苏能在节点 uu 放上梅花当且仅当满足如下条件:

扶苏当前在节点 uu

对于 uu 的所有孩子 vv,节点 vv 被放上了 wvw_v 朵梅花。

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

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

输入格式

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

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

第二行有 n1n-1 个用空格隔开的整数,第 ii 个整数 pip_i 代表第 i+1i+1 号节点的家长节点编号。

第三行有 nn 个用空格隔开的整数,第 ii 个整数代表 wiw_i

输出格式

输出一行 nn 个用空格隔开的整数,第 ii 个整数代表想在 ii 号节点上放 wiw_i 朵梅花需要准备的梅花个数。

3 
1 2 
1 1 1
2 2 1
3
1 1
1 1 1
3 1 1
6
1 1 2 3 4
3 14 1 5 12 15
21 20 13 20 12 15

提示

输入输出样例 1 解释

qwq

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

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

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

输入输出样例 3 解释

qwq

样例 3 的输入如左图。

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

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

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

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


数据规模与约定

测试点编号 n=n = 测试点编号 n=n =
1 11 11 100003100003
2 88 12
3 13
4 14
5 15 100004100004
6 100000100000 16
7 17
8 100002100002 18
9 19
10 20
  • 对于测试点 5、6,满足特殊性质:每个节点的孩子结点个数不超过 22
  • 对于测试点 8 到测试点 10,满足特殊性质:每个节点的孩子节点个数不超过 55
  • 对于测试点 11 到测试点 14,满足特殊性质:任意一个节点到根的路径上的点数不超过 33,也即树高不超过 33
  • 对于 100%100\% 的数据,保证 $1 \leq n \leq 10^5 + 4,~1 \leq p_i \leq i,~1 \leq w_i \leq 1000$。

提示

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