定义：树是一个有n个点n − 1条边的无向连通图，任意两个点间恰有一条简单路径。最末端仅有一条边相连的节点称为叶子。
小C 家有一个后院，院子的中央种有一棵树。小C 喜欢在雨后初晴时到院子里观察。这棵参天大树可以抽象成一棵n 个节点的树，节点从1 到n 编号，树的根在1 号节点。第
i 个节点有一个正整数ai 表示该处的美感值。小C 尤其喜欢观察蚂蚁。这天，小C 捉来了m 只蚂蚁。他想挑选树上的m 个节点，每个节点放上一只蚂蚁。小 C 知道蚂蚁在树上时，会一直朝着根的方向移动，中间会经过一个个节点，最后到达根节点，之后，蚂蚁便到达了地面。
热爱自然的小C 想知道这m 只蚂蚁经过的节点的美感值和的最大值是多少，于是请你来帮帮忙。注意经过的节点包括初始节点，且多次访问的节点仅算入一次.。
3673: 2020-4-小 C 的树（tree）-初中组
| Time Limit | $8$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $8$ | 正确数量 | $5$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
共三行，第一行有两个正整数n,m，表示树的大小和选取的节点数；
第二行有n 个非负整数，第i 个数表示ai；
第三行有n − 1 个正整数，第i 个数fi 表示节点i + 1 的父亲节点。保证0 < fi ≤ i。
第二行有n 个非负整数，第i 个数表示ai；
第三行有n − 1 个正整数，第i 个数fi 表示节点i + 1 的父亲节点。保证0 < fi ≤ i。
Output
仅一行一个数，表示美感值和的最大值。
Sample Input复制
5 2
1 2 3 1 3
1 1 2 2
Sample Output复制
9
提示
【样例1 解释】
这棵树的形态如下图：
选择{3, 5} 两个节点，则经过的节点集合为{1, 2, 3, 5}。
红色数字为每个节点的美感值，故美感值和为1 + 2 + 3 + 3 = 9。可以证明这个值是最大值。
【数据范围】
对于所有数据：0 < m ≤ n ≤ 5 × 106，0 ≤ ai ≤ 5。
部分测试点放n = 的形式，方便选手直接判断是否为对应测试点。
【提示】
如有需要，请使用scanf 读入以及减少使用STL，以降低程序本身带来的常数。
这棵树的形态如下图：
选择{3, 5} 两个节点，则经过的节点集合为{1, 2, 3, 5}。
红色数字为每个节点的美感值，故美感值和为1 + 2 + 3 + 3 = 9。可以证明这个值是最大值。
【数据范围】
| 测试点 | n | 特殊性质 |
|
1 |
=5 |
无 |
| 2 | =20 | |
| 3 | <=300 | |
| 4 | =2997 | 叶子数=n-1 |
| 5 | <=5000 | ai=1 |
| 6 | <=8000 | 无 |
| 7 | <=299998 | 叶子数<=20 |
| 8 | <=3*105 |
无 |
| 9 | <=106 | |
| 10 | <=5*106 |
部分测试点放n = 的形式，方便选手直接判断是否为对应测试点。
【提示】
如有需要，请使用scanf 读入以及减少使用STL，以降低程序本身带来的常数。
推荐代码 查看3673 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$5519 $ms] | ldy6314 | 765359 | 2021-10-13 08:02:40 |
| 内存最少[$267272 $KB] | ldy6314 | 765365 | 2021-10-13 09:24:35 |
| 第一AC | ldy6314 | 765347 | 2021-10-12 23:31:13 |
| 第一挑战 | ldy6314 | 764358 | 2021-10-09 22:54:36 |
赛题来源/所属竞赛 S:合肥市信息学 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|