Monopoly on a Tree

This problem is a twist on the classical board game. In this game, the board is given as a rooted tree with \(n\) nodes (node 1 is the root) and each node \(x\) has a price \(w_x\). We say that for two different nodes \(x\) and \(y\), if \(x\) is an ancestor of \(y\) (i.e. \(x\) lies on the simple path from node 1 to \(y\)), then \(x\) dominates \(y\).

The game is played by two players, W and H. They take turns buying an unpurchased node until every node is owned. When a player buys a node \(x\), the following happens:

• The buyer pays the system \(w_x\) coins.
• Let \(n_1\) be the number of nodes that \(x\) dominates which have already been bought by the opponent, and \(n_2\) be the number of nodes that dominate \(x\) which have already been bought by the opponent.
• If \(n_1 > n_2\) then the opponent pays \(n_1 - n_2\) coins to the buyer, and if \(n_1 < n_2\) then the buyer pays \(n_2 - n_1\) coins to the opponent.

Both players are assumed to be absolutely brilliant and will play optimally to maximize their net profit. The net profit for player W is defined as the coins he receives from H minus the coins he pays (to both the system and H) over the course of the game. Note that the answer may be negative. If player W goes first, what is his final net profit under optimal play?

Game summary:

• The board is a tree with \(n\) nodes; node 1 is the root.
• Each node \(x\) has a price \(w_x\).
• For any two different nodes \(x,y\), if \(x\) is an ancestor of \(y\), we say \(x\) dominates \(y\).
• The players W and H take turns buying nodes (W goes first); once a node is purchased it cannot be purchased again.
• When buying node \(x\), the buyer pays \(w_x\) coins, and then a bonus (or penalty) is calculated based on already purchased nodes by the opponent that are in a dominating relationship with \(x\): let \(n_1\) be the number of opponent nodes that are dominated by \(x\) and \(n_2\) be the number of opponent nodes that dominate \(x\). If \(n_1>n_2\), the opponent pays \(n_1-n_2\) coins to the buyer; otherwise the buyer pays \(n_2-n_1\) coins to the opponent.
• The final net profit for W is the coins W gets from H minus the coins W pays (both to the system and to H).

inputFormat

The input begins with an integer \(n\) (the number of nodes). The next line contains \(n\) integers \(w_1, w_2, \ldots, w_n\) denoting the price of each node. Then follow \(n-1\) lines; the \(i\)-th of these lines (for \(i=2,3,\ldots,n\)) contains one integer \(p_i\), which is the parent of node \(i\) in the tree (the tree is rooted at node 1).

outputFormat

Output a single integer, the final net profit for player W if both W and H play optimally.

sample

1
10

-10