Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-树上选点
题目 3184:

蓝桥杯2023年第十四届省赛真题-树上选点

时间限制: 3s 内存限制: 520MB 提交: 662 解决: 132

题目描述

给定一棵树,树根为 1,每个点的点权为 Vi 。 

你需要找出若干个点 Pi,使得:

1. 每两个点 Px Py 互不相邻;

2. 每两个点 Px Py 与树根的距离互不相同;

3. 找出的点的点权之和尽可能大。 

请输出找到的这些点的点权和的最大值。 

输入格式

输入的第一行包含一个整数 n 。 

第二行包含 n − 1 个整数 Fi ,相邻整数之间使用一个空格分隔,分别表示 第 2 至 n 个结点的父结点编号。 

第三行包含 n 个整数 Vi,相邻整数之间使用一个空格分隔,分别表示每个结点的点权。 

输出格式

输出一行包含一个整数表示答案。 

样例输入

5
1 2 3 2
2 1 9 3 5

样例输出

11

提示

对于40%的评测用例,n ≤ 5000 ; 

对于所有评测用例,1 ≤ n ≤ 2 × 105,1 ≤ Fi < i,1 ≤ Vi ≤ 104 。 

标签