题目描述 给定一棵树，树根为 1，每个点的点权为 Vi 。 你需要找出若干个点 Pi，使得： 1. 每两个点 Px Py 互不相邻； 2. 每两个点 Px Py 与树根的距离互不相同； 3. 找出的点的点权之和尽可能大。 请输出找到的这些点的点权和的最大值。 输入格式 输入的第一行包含一个整数 n 。 第二行包含 n − 1 个整数 Fi ，相邻整数之间使用一个空格分隔，分别表示 第 2 至 n 个结点的父结点编号。 第三行包含 n 个整数 Vi，相邻整数之间使用一个空格分隔，分别表示每个结点的点权。 输出格式 输出一行包含一个整数表示答案。

这是一道经典的树形 DP 题目，可以使用树形背包算法解决。具体来说，我们可以设计一个状态 f[i][j]，表示在以 i 为根的子树中，选取若干个点，它们的点权之和为 j 时，能够达到的最大距离（其中距离指的是选取的点到根结点的距离）。对于每个结点 i，我们可以考虑两种情况：

1.不选 i 结点，此时 f[i][j] 的值等于以 i 的每个儿子结点为根结点的子树中能够选出点权之和为 j 的最大距离；

2.选 i 结点，此时 f[i][j] 的值等于以 i 的每个儿子结点为根结点的子树中能够选出点权之和为 j-v[i] 的最大距离加上 v[i]，其中 v[i] 表示 i 结点的点权。

最终的答案为 f[1][j] 中最大的满足 j≤n 的值 j。

时间复杂度

树形背包算法的时间复杂度为 O(n^2)，其中 n 是树中结点的个数。

参考代码

下面的代码中，dp[i][j] 表示在以 i 为根的子树中，选取若干个点，它们的点权之和为 j 时，能够达到的最大距离。代码中的 dfs 函数用于计算以 i 为根的子树的 dp 值，其中 u 表示当前处理的儿子结点编号。