开始 2019-06-14 16:00:00

517编程-OI赛制测试赛-提高组

结束 2019-06-14 20:00:00
Contest is over.
当前 2020-06-05 20:10:06

C. 树上的石头

描述

给你一棵树,标号为0到n-1,0为根节点,每个点有点权

现在你可以在一些点上放石头,也可以拿掉某些点上的石头

一个点可以放石头当且仅当这个点的所有儿子都放上了石头

如果根节点放上石头任务完成

求在整个过程中放着石头的节点的点权之和的最大值的最小值( 也就是说你要选择一个合理的顺序放置石头来使得答案最优)

输入

第一行输入一个整数$n$ ($2 \le n \le 1000$)
 

第二行输入$n-1$个整数$p[0]->p[n-2]$, $p[i]$表示$(i+1)$与$p[i]$之间有一条边,$0 \le p[i] \le i$
 

第三行输入n个整数表示每个点的点权,$1 \le w[i] \le 10^5$ , w非减
 

输出

输出一个整数

样例

输入

5
0 1 2 3
1 2 2 4 4

输出

8

输入

5
0 0 0 0 
1 2 3 4 5

输出

15

提示

30分: n <= 20

30分: n <= 100

40分: 无限制

 

样例一解释:
 

{0,1,2,3} //分别表示1的父亲 2的父亲 3的父亲 4的父亲

{1,2,2,4,4}//每个点的点权值

Returns: 8

五个节点构成了一条链

在节点4上放一个石头 (权值和 = 4).

在节点3上放一个石头 (权值和 = 8).

移除节点4上的石头   (权值和 = 4).

在节点2上放一个石头 (权值和 = 6).

在节点1上放一个石头 (权值和 = 8).

移除节点2上的石头   (权值和 = 6)

在节点0(根节点)上放一个石头 (权值和 = 7)

整个过程中最大的权值和为8,不存在比最大值比8小的方案了

时间限制 1 秒
内存限制 128 MB