2123: [蓝桥杯2023初赛] 树上选点

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:251 通过:14

题目描述

给定一棵树,树根为 1,每个点的点权为 Vi 。
你需要找出若干个点 Pi,使得:
1. 每两个点 Px, Py 互不相邻;
2. 每两个点 Px, Py 与树根的距离互不相同;
3. 找出的点的点权之和尽可能大。
请输出找到的这些点的点权和的最大值。

输入格式

输入的第一行包含一个整数 n 。
第二行包含 n-1 个整数 Fi ,相邻整数之间使用一个空格分隔,分别表示第 2 至 n 个结点的父结点编号。
第三行包含 n 个整数 Vi,相邻整数之间使用一个空格分隔,分别表示每个结点的点权。
对于40% 的评测用例,n ≤ 5000 ;
对于所有评测用例,1 ≤ n ≤ 2×100000, 1 ≤ Fi < i,1 ≤ Vi ≤ 10000 。

输出格式

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

输入样例 复制

5
1 2 3 2
2 1 9 3 5

输出样例 复制

11