/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は、ある会社の組織図を分析しています。
この会社の組織は N 人の社員からなり、組織図は根付き木で表されます。社員には 1 から N までの番号が付けられており、社員 1 が社長（根）です。各社員 i（2 \leq i \leq N）には直属の上司 P_i がおり、社員 i は社員 P_i の直属の部下です。
各社員 i には担当する仕事量を表す非負整数 W_i が割り当てられています。直属の部下を 1 人以上持つ社員（管理職）については W_i = 0 であることが保証されています。直属の部下を持たない社員（一般社員、すなわち木の葉に対応する社員）については W_i \geq 0 です（W_i = 0 の場合もあります）。
まず、各社員 u に対して、社員 u の チーム仕事量 S_u を、社員 u を根とする部分木に含まれるすべての社員（u 自身を含む）の仕事量の総和と定義します。すなわち、S_u = \displaystyle\sum_{v} W_v（和は社員 u を根とする部分木に含まれるすべての社員 v について取る）です。
次に、各社員 v の アンバランス度 を以下のように定義します。
- 社員 v の直属の部下が 2 人以上いるとき：直属の部下たちのチーム仕事量の最大値と最小値の差。すなわち、社員 v の直属の部下の集合を \{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
- 1 行目には、社員の数を表す整数 N が与えられる。
- 2 行目には、社員 2 から社員 N までの直属の上司の番号 P_2, P_3, \ldots, P_N が N - 1 個、空白区切りで与えられる。N = 1 のとき、この行は空行となる。
- 3 行目には、各社員の仕事量 W_1, W_2, \ldots, W_N が N 個、空白区切りで与えられる。
出力
組織全体のアンバランス度（すべての社員のアンバランス度の最大値）を 1 行で出力せよ。
入力例 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
Score : 366 pts
Problem Statement
Takahashi is analyzing the organizational chart of a company.
The organization consists of N employees, and the organizational chart is represented as a rooted tree. The employees are numbered from 1 to N, and employee 1 is the president (root). Each employee i (2 \leq i \leq N) has a direct supervisor P_i, meaning employee i is a direct subordinate of employee P_i.
Each employee i is assigned a non-negative integer W_i representing their workload. It is guaranteed that for employees who have one or more direct subordinates (managers), W_i = 0. For employees who have no direct subordinates (regular employees, i.e., employees corresponding to leaves of the tree), W_i \geq 0 (including the case W_i = 0).
First, for each employee u, define the team workload S_u of employee u as the sum of the workloads of all employees (including u themselves) in the subtree rooted at employee u. That is, S_u = \displaystyle\sum_{v} W_v (where the sum is taken over all employees v in the subtree rooted at employee u).
Next, define the imbalance of each employee v as follows:
- When employee v has 2 or more direct subordinates: the difference between the maximum and minimum team workloads among the direct subordinates. That is, if the set of direct subordinates of employee v is \{c_1, c_2, \ldots, c_k\} (k \geq 2), then \max(S_{c_1}, \ldots, S_{c_k}) - \min(S_{c_1}, \ldots, S_{c_k}).
- When employee v has 1 or fewer direct subordinates (this includes both managers with exactly 1 direct subordinate and regular employees with no direct subordinates): 0.
Define the imbalance of the entire organization as the maximum imbalance among all employees.
Find the imbalance of the entire organization.
Constraints
- 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)
- When employee i has direct subordinates (is not a leaf), W_i = 0
- All input values are integers
Input
N P_2 P_3 \cdots P_N W_1 W_2 \cdots W_N
- The first line contains an integer N representing the number of employees.
- The second line contains N - 1 integers P_2, P_3, \ldots, P_N, the direct supervisor numbers for employees 2 through N, separated by spaces. When N = 1, this line is an empty line.
- The third line contains N integers W_1, W_2, \ldots, W_N, the workloads of each employee, separated by spaces.
Output
Output the imbalance of the entire organization (the maximum imbalance among all employees) on a single line.
Sample Input 1
3 1 1 0 10 3
Sample Output 1
7
Sample Input 2
7 1 1 2 2 3 3 0 0 0 8 2 9 1
Sample Output 2
8
Sample Input 3
10 1 1 1 2 2 3 4 4 4 0 0 0 0 20 5 12 100 3 1
Sample Output 3
99