The Charge Game on a Binary Tree

There is a rooted binary tree with \(n\) nodes. Each node \(i\) has a capacity \(c_i\) (i.e. it can hold at most \(c_i\) balls) and is initially empty. A node is said to be full if the number of balls in it equals its capacity.

A game is played on this tree between a mortal and a god. In each round the mortal drops a ball from the root. Each ball carries either a +1 or -1 unit charge, chosen by the mortal. As the ball falls along the tree, the following rules are applied at each visited node:

• If the node has no children or all of its children are full, the ball stops at that node and the node’s ball count increases by one.
• If the node has exactly one child that is not full, the ball falls to that child.
• If the node has two children that are not full, then let the charge algebra sum in a subtree be defined as the (number of +1 charges) minus (number of -1 charges) in that subtree. Suppose the two children are the left and right child. Then:
  • If \(S_{L} > S_{R}\), the ball falls to the right child if it carries a +1 charge and to the left child if it carries a -1 charge.
  • If \(S_{L} < S_{R}\), the ball falls to the left child if it carries a +1 charge and to the right child if it carries a -1 charge.
  • If \(S_{L} = S_{R}\), then the god chooses the direction.

Before the game begins, the players agree on a target node \(u\) (\(1 \le u \le n\)). In each round, the mortal chooses the charge of the ball, and the god guides its falling (using the rules above) with the aim of maximally delaying when \(u\) gets full, while the mortal wants to finish the game as soon as possible. The game ends as soon as node \(u\) becomes full, and we denote the number of rounds required as \(r_u\).

If both players play optimally, it turns out that regardless of the charge details the process is determined by a postorder filling order induced by the tree structure. In fact, note that a ball never stops at an internal node until all of its children are full. Therefore, if we define a function \(F(u)\) as the total number of balls needed to completely fill the subtree rooted at \(u\) under the delaying strategy of the god, we have:

• If \(u\) is a leaf, \(F(u) = c_u\).
• If \(u\) has only one child \(v\), then \(F(u) = F(v) + c_u\).
• If \(u\) has two children (left and right), then \(F(u) = F(left) + F(right) + c_u\).

Moreover, if the target node \(u\) is not the root, the adversary (god) can always force diversion at every branching on the unique path from the root to \(u\). Specifically, for every ancestor \(v\) of \(u\) that has two children, if the child on the path to \(u\) is known then the other child (say, \(w\)) will be filled entirely first, consuming \(F(w)\) rounds. Therefore, for any target node \(u\) with ancestors \(a_1, a_2, \dots, a_k = u\) (where \(a_1\) is the root), the number of rounds required is:

[ r_u = \Bigl( \sum_{v \in P \setminus {u} \text{ with two children}} F(\text{off}(v)) \Bigr) + F(u), ]

where \(F(\text{off}(v))\) denotes the filling cost of the child of \(v\) that is not on the path from the root to \(u\). (If a node has only one child, no diversion is possible.)

Your task is: Given the tree and the capacities, for each \(1 \le u \le n\), compute \(r_u\) under optimal play by both sides.

Input format:

• The first line contains a single integer \(n\) (the number of nodes).
• The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\) where \(c_i\) is the capacity of node \(i\).
• The next \(n\) lines describe the tree. The \(i\)-th of these lines contains two integers \(l_i\) and \(r_i\), the indices of the left and right children of node \(i\) respectively. If a child does not exist, its index is given as 0.

Output format:

• Output \(n\) lines. The \(i\)-th line should contain the number \(r_i\), i.e. the number of rounds required if node \(i\) is chosen as the target.

Note: Both the mortal and the god play optimally. The mortal’s choices cannot force an earlier filling of a node if a non‐target branch is available (because of the rules), and the god will always steer the ball away from the target whenever possible.

inputFormat

The input begins with a line containing a single integer \(n\) (the number of nodes).

The second line contains \(n\) space-separated integers \(c_1, c_2, \dots, c_n\) representing the capacity of each node.

Then follow \(n\) lines; the \(i\)-th line contains two integers \(l_i\) and \(r_i\) denoting the indices of the left and right child of node \(i\) respectively (use 0 if a child does not exist). The tree is rooted at node 1.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain the number \(r_i\): the rounds required to fill node \(i\) under optimal play.

sample

2
1 1
2 0
0 0

2
1

</p>