树上最大权值和路径
练习 1：树上最大权值和路径
题目描述：
给定一棵以 1 为根的有根树，每个结点有一个权值 w[i]（可能为负数）。现在要选择一条从根到某个叶子的路径，使得路径上所有结点权值之和最大。
输入格式：
- 第一行：一个正整数
n（2 ≤ n ≤ 1000） - 第二行：
n-1个正整数f_2, f_3, ..., f_n，其中f_i表示结点i的父结点编号 - 第三行：
n个整数w[1], w[2], ..., w[n]（-1000 ≤ w[i] ≤ 1000）
输出格式：
- 一行，一个整数，表示最大路径权值和
样例输入：
5
1 1 2 2
10 -5 8 3 -2
样例输出：
18
样例解释：
树的结构：
10
/ \
-5 8
/ \
3 -2
路径 1 → 2 → 4 的权值和为 10 + (-5) + 3 = 8
路径 1 → 2 → 5 的权值和为 10 + (-5) + (-2) = 3
路径 1 → 3 的权值和为 10 + 8 = 18（最大）
提示：
- DFS 递归：
dfs(u)返回从u到其子树中某个叶子的最大路径和 - 转移：
dp[u] = w[u] + max(0, max(dp[v]))（如果子树贡献为负，可以不要） - 或者直接 DFS 时维护从根到当前结点的路径和，到叶子时更新答案