Problem 3673 --2020-4-小 C 的树(tree)-初中组

3673: 2020-4-小 C 的树(tree)-初中组

"
Time Limit $8$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $8$ 正确数量 $5$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
    定义:树是一个有n个点n − 1条边的无向连通图,任意两个点间恰有一条简单路径。最末端仅有一条边相连的节点称为叶子。
    小C 家有一个后院,院子的中央种有一棵树。小C 喜欢在雨后初晴时到院子里观察。这棵参天大树可以抽象成一棵n 个节点的树,节点从1 到n 编号,树的根在1 号节点。第
i 个节点有一个正整数ai 表示该处的美感值。小C 尤其喜欢观察蚂蚁。这天,小C 捉来了m 只蚂蚁。他想挑选树上的m 个节点,每个节点放上一只蚂蚁。小 C 知道蚂蚁在树上时,会一直朝着根的方向移动,中间会经过一个个节点,最后到达根节点,之后,蚂蚁便到达了地面。
    热爱自然的小C 想知道这m 只蚂蚁经过的节点的美感值和的最大值是多少,于是请你来帮帮忙。注意经过的节点包括初始节点,且多次访问的节点仅算入一次.。
共三行,第一行有两个正整数n,m,表示树的大小和选取的节点数;
第二行有n 个非负整数,第i 个数表示ai;
第三行有n − 1 个正整数,第i 个数fi 表示节点i + 1 的父亲节点。保证0 < fi ≤ i。
仅一行一个数,表示美感值和的最大值。
5 2
1 2 3 1 3
1 1 2 2
9
【样例1 解释】
这棵树的形态如下图:

选择{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
对于所有数据:0 < m ≤ n ≤ 5 × 106,0 ≤ ai ≤ 5
部分测试点放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

竞赛编号 竞赛名称 竞赛时间 访问比赛