← 返回题目列表

AtCoder · awc0043_c

C. 组织失衡

中文机器翻译题面 查看原题

分数: 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