题目描述 给定一棵树，树根为 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 表示当前处理的儿子结点编号。

相关问题

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

您好，这是一道经典的树形 DP 问题，可以按照以下步骤来解决：

1. 对于每个节点，分别计算选它和不选它时子树内能够得到的最大值。设 f(i,1) 表示选择第 i 个节点时其子树内能够得到的最大值，f(i,0) 表示不选择第 i 个节点时其子树内能够得到的最大值。则有以下递推式：

f(i,1) = Vi + ∑f(j,0)，其中 j 是 i 的每个子节点；
f(i,0) = ∑max(f(j,0), f(j,1))，其中 j 是 i 的每个子节点。

2. 根据上述递推式，从根节点开始逆推，计算每个节点选或不选的最大值（即 f(i,0) 和 f(i,1) 中的较大值），直到递推到根节点为止。

3. 最后根据根节点选或不选的最大值（即 f(1,0) 和 f(1,1) 中的较大值），即可得到最大点权和。

下面是该问题的代码实现：

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

可以使用动态规划来解决这个问题。设 f(i,0) 表示在以 i 为根的子树中，不选 i 的情况下，其他符合要求的点的最大点权和；f(i,1) 表示在以 i 为根的子树中，选了 i 的情况下，其他符合要求的点的最大点权和。则有如下转移方程：

f(i,0) = sum(max(f(j,0),f(j,1)))，其中 j 是 i 的儿子节点
f(i,1) = Vi + sum(f(j,0))，其中 j 是 i 的孙子节点

最终的答案为 max(f(1,0), f(1,1))，即以根节点为起点的结果。

下面是代码实现：

n = int(input())
val = list(map(int, input().split()))

head = [0] * (n + 1)
edge = []
idx = 0
for i in range(1, n):
    u, v = map(int, input().split())
    edge.append((v, head[u]))
    head[u] = idx
    idx += 1
    edge.append((u, head[v]))
    head[v] = idx
    idx += 1

f = [[0] * 2 for _ in range(n + 1)]

def dfs(u, fa):
    f[u][1] = val[u-1]
    for i in range(head[u]):
        v = edge[head[u]+i][0]
        if v == fa:
            continue
        dfs(v, u)
        f[u][1] += f[v][0]
        f[u][0] += max(f[v][0], f[v][1])
    return

dfs(1, 0)
print(max(f[1][0], f[1][1]))