/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君と青木君は、王国の領地をめぐる争奪戦を行っています。
王国には N 個の都市があり、都市には 1 から N までの番号が付いています。都市同士は道路で結ばれており、全体として根付き木の構造をしています。都市 1 は王都であり、木の根にあたります。各都市 i（2 \leq i \leq N）の親都市は都市 P_i です。各都市 i（1 \leq i \leq N）には、その都市の資源価値を表す整数 V_i が定められています。資源価値は負であることもあり、その場合は占領すると損失が生じることを意味します。
争奪戦は「道路の封鎖」と「占領ゲーム」の 2 つのフェーズからなります。
フェーズ 1：道路の封鎖
占領ゲームの前に、青木君には特別な権限が与えられています。青木君は木の構造と各都市の資源価値をすべて見た上で、木に含まれる辺（道路）を ちょうど 1 本選んで封鎖するか、または 1 本も封鎖しないかを選べます。ただし、木に辺が存在しない場合（N = 1 の場合）は封鎖しない一択です。
道路を 1 本封鎖すると、木は 2 つの連結成分に分かれます。このとき、王都（都市 1）を含む連結成分のみが占領ゲームの対象となり、もう一方の連結成分に属する都市と道路はゲームから取り除かれます。ゲームの対象となる木の根は引き続き都市 1 であり、残った都市間の親子関係は元の木における親子関係がそのまま引き継がれます。道路を封鎖しない場合は、元の木全体がゲームの対象です。
フェーズ 2：占領ゲーム
道路の封鎖が行われた後、ゲームの対象となるすべての都市は未占領の状態から始まります。2 人は交互に手番を行い、高橋君が先手です。
ある都市が 占領可能 であるとは、以下の条件をともに満たすことをいいます。
- その都市が現在未占領である。
- その都市が王都（都市 1）であるか、またはその都市の親都市がすでに占領済みである。
ここで「占領済み」とは、高橋君・青木君のいずれかによって過去の手番で占領されたことを意味します。占領可能かどうかの判定において、その都市の親を占領したのが高橋君か青木君かは区別しません。王都は親を持たないため、未占領である限り常に占領可能です。
手番が回ってきたとき、占領可能な都市が 1 つ以上存在するならば、手番のプレイヤーはその中からちょうど 1 つを選んで占領しなければなりません（パスは認められません）。占領可能な都市が 1 つも存在しなくなった時点で、ゲームは直ちに終了します。
目的
ゲーム終了時、占領された都市全体の集合を S とします。
高橋君は資源価値の合計 \displaystyle\sum_{i \in S} V_i を最大化したく、青木君はこの同じ値を最小化したいです。
青木君はフェーズ 1 の道路の封鎖を最適に行い、フェーズ 2 の占領ゲームでも最適にプレイします。高橋君もフェーズ 2 で最適にプレイします。
両者がすべての選択を最適に行ったとき、ゲーム終了時の \displaystyle\sum_{i \in S} V_i の値を求めてください。
制約
- 1 \leq N \leq 5 \times 10^5
- -10^9 \leq V_i \leq 10^9
- 1 \leq P_i < i （2 \leq i \leq N）
- 入力はすべて整数である。
入力
N V_1 V_2 \ldots V_N P_2 P_3 \ldots P_N
- 1 行目には、都市の数を表す整数 N が与えられる。
- 2 行目には、各都市の資源価値を表す N 個の整数 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。
- 3 行目には、都市 2, 3, \ldots, N の親都市を表す N - 1 個の整数 P_2, P_3, \ldots, P_N がスペース区切りで与えられる。P_i は都市 i の親の都市番号である。N = 1 の場合、3 行目は存在しない（入力は 2 行のみである）。
出力
両者が最適にプレイしたときの、占領された都市の資源価値の合計を 1 行で出力せよ。
入力例 1
3 5 -2 4 1 1
出力例 1
3
入力例 2
5 3 8 -5 2 -10 1 2 2 3
出力例 2
-4
入力例 3
12 10 -4 7 3 -8 6 -2 5 -1 9 -6 4 1 1 2 2 3 3 4 6 6 7 10
出力例 3
5
入力例 4
30 12 -7 25 -30 8 14 -5 19 -11 6 -3 21 -17 4 10 -9 13 -2 7 -15 18 -6 5 -12 9 -4 16 -20 11 -8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
出力例 4
12
入力例 5
1 -1000000000
出力例 5
-1000000000
Score : 400 pts
Problem Statement
Takahashi and Aoki are engaged in a battle over the territory of a kingdom.
The kingdom consists of N cities, numbered 1 to N. The cities are connected by roads, forming a rooted tree structure as a whole. City 1 is the capital and serves as the root of the tree. For each city i (2 \leq i \leq N), its parent city is City P_i. Each city i (1 \leq i \leq N) has an integer V_i representing its resource value. The resource value can be negative, which means occupying it will result in a loss.
The battle consists of two phases: "Road Blockade" and "Occupation Game".
Phase 1: Road Blockade
Before the occupation game begins, Aoki is given a special authority. After looking at the tree structure and all resource values of the cities, Aoki can choose to block exactly one edge (road) in the tree, or block no edges at all. However, if there are no edges in the tree (i.e., when N = 1), he must choose not to block any.
If a road is blocked, the tree is split into two connected components. At this point, only the connected component containing the capital (City 1) will be used for the occupation game, and the cities and roads in the other connected component are removed from the game. The root of the tree used for the game remains City 1, and the parent-child relationships among the remaining cities are inherited directly from the original tree. If no road is blocked, the entire original tree is used for the game.
Phase 2: Occupation Game
After the road blockade phase, all cities in the game start in an unoccupied state. The two players take turns, with Takahashi going first.
A city is said to be occupiable if it satisfies both of the following conditions:
- The city is currently unoccupied.
- The city is the capital (City 1), or its parent city is already occupied.
Here, "occupied" means the city has been occupied by either Takahashi or Aoki in a previous turn. In determining whether a city is occupiable, it does not matter whether Takahashi or Aoki occupied its parent. Since the capital has no parent, it is always occupiable as long as it is unoccupied.
On a player's turn, if there is at least one occupiable city, the player must choose and occupy exactly one of them (passing is not allowed). The game ends immediately when there are no more occupiable cities.
Objective
Let S be the set of all occupied cities at the end of the game.
Takahashi wants to maximize the total resource value \displaystyle\sum_{i \in S} V_i, and Aoki wants to minimize this same value.
Aoki will optimally perform the road blockade in Phase 1 and play optimally in the Phase 2 occupation game. Takahashi will also play optimally in Phase 2.
Find the value of \displaystyle\sum_{i \in S} V_i at the end of the game when both players make all their choices optimally.
Constraints
- 1 \leq N \leq 5 \times 10^5
- -10^9 \leq V_i \leq 10^9
- 1 \leq P_i < i (2 \leq i \leq N)
- All input values are integers.
Input
N V_1 V_2 \ldots V_N P_2 P_3 \ldots P_N
- The first line contains an integer N, representing the number of cities.
- The second line contains N space-separated integers V_1, V_2, \ldots, V_N, representing the resource values of each city.
- The third line contains N - 1 space-separated integers P_2, P_3, \ldots, P_N, representing the parent cities of cities 2, 3, \ldots, N. P_i is the parent city number of city i. If N = 1, the third line does not exist (the input has only two lines).
Output
Print the total resource value of the occupied cities when both players play optimally in a single line.
Sample Input 1
3 5 -2 4 1 1
Sample Output 1
3
Sample Input 2
5 3 8 -5 2 -10 1 2 2 3
Sample Output 2
-4
Sample Input 3
12 10 -4 7 3 -8 6 -2 5 -1 9 -6 4 1 1 2 2 3 3 4 6 6 7 10
Sample Output 3
5
Sample Input 4
30 12 -7 25 -30 8 14 -5 19 -11 6 -3 21 -17 4 10 -9 13 -2 7 -15 18 -6 5 -12 9 -4 16 -20 11 -8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Sample Output 4
12
Sample Input 5
1 -1000000000
Sample Output 5
-1000000000