分数: 366 分
问题陈述
高桥正在分析一家公司的组织结构图。
该组织包括 N 员工,组织结构图表示为有根树。员工编号从 1 to N和员工 1 是主席(root)。每位员工 i (2 \leq i \leq N) 有直接主管 P_i,意思是员工 i 是员工的直属下属 P_i.
每位员工 i 被分配一个非负整数 W_i 代表他们的工作量。保证对于有一名或多名直接下属(经理)的员工, W_i = 0。对于没有直接下属的员工(正式员工,即树的叶子对应的员工), W_i \geq 0 (包括案例 W_i = 0).
首先,对于每个员工 u,定义 团队工作量 员工的 S_u 员工的 u 作为所有员工的工作量总和(包括 u 他们自己)位于以员工为根的子树中 u。也就是说, S_u = \displaystyle\sum_{v} W_v (总和涵盖所有员工 v 在以员工为根的子树中 u).
接下来,定义 不平衡 每位员工的 每位员工的 v 如下:
- 当员工 v 有 正面写有 2 或更多直属下属:直属下属之间的最大和最小团队工作量之间的差异。也就是说,如果员工的直接下属集合 v is \{c_1, c_2, \ldots, c_k\} (k \geq 2),然后 \max(S_{c_1}, \ldots, S_{c_k}) - \min(S_{c_1}, \ldots, S_{c_k}).
- 当员工 v 有 正面写有 1 或更少的直接下属(这包括两位经理) 1 直属下属和无直属下属的正式员工): 0.
定义 不平衡 每位员工的 整个组织的所有员工之间的最大不平衡。
找出整个组织的不平衡性。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
- 0 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 当员工 i 有直接下属(不是叶子), W_i = 0
- 所有输入值均为整数
输入
N P_2 P_3 \cdots P_N W_1 W_2 \cdots W_N
- 第一行包含一个整数 N 代表员工人数。
- 第二行包含 N - 1 整数 P_2, P_3, \ldots, P_N,员工的直接主管号码 2 通过 N,用空格分隔。当 N = 1,这一行是空行。
- 第三行包含 N 整数 W_1, W_2, \ldots, W_N,每个员工的工作量,用空格分隔。
输出
在一条线上输出整个组织的不平衡度(所有员工之间的最大不平衡度)。
示例输入 1
3 1 1 0 10 3
示例输出 1
7
示例输入 2
7 1 1 2 2 3 3 0 0 0 8 2 9 1
示例输出 2
8
示例输入 3
10 1 1 1 2 2 3 4 4 4 0 0 0 0 20 5 12 100 3 1
示例输出 3
99