Optimal Rounds in the Ball‐Dropping Game on a Binary Tree

There is a rooted binary tree with \( n \) nodes. Each node \( i \) has a capacity \( c_i \), and initially every node contains 0 balls. A node is said to be full once the number of balls deposited there equals its capacity.

A game is played on the tree between a mortal and a deity. In each round the mortal chooses to drop a ball from the root. Each ball carries either a \( +1 \) unit (positive) or a \( -1 \) unit (negative) charge, as chosen by the mortal. As the ball falls, its path is determined by the following rules at every node:

• If the current node has no children, or if all of its children are full, the ball stops at this node. Its arrival increases the ball count by 1 at that node (and the net charge of the node is increased by the ball’s charge).
• If the node has exactly one child that is not full, the ball falls to that one child.
• If the node has two children that are both not full, let \( S_L \) and \( S_R \) denote the charge algebraic sums (i.e. the number of positive balls minus the number of negative balls) in the entire left and right subtrees respectively. Then:
  • If \( S_L > S_R \): the ball falls to the right child if its charge is \( +1 \), and to the left child if its charge is \( -1 \).
  • If \( S_L < S_R \): the ball falls to the left child if its charge is \( +1 \), and to the right child if its charge is \( -1 \).
  • If \( S_L = S_R \): the deity chooses the child through which the ball falls.

Before the game starts, both players agree on a target node \( u \) (\( 1\le u\le n \)). In each round, the mortal picks the ball’s charge while the deity, following the above rules, controls its descent. The game ends as soon as the target node \( u \) becomes full.

The mortal wants the game to finish in as few rounds as possible while the deity wants to prolong it. Assuming both players play optimally, for every \( u \) from \( 1 \) to \( n \), determine the number of rounds \( r_u \) the game will last.

Note: If at a decision point the rule depends on subtree charge sums, the subtree sum for a node is defined as the algebraic sum of charges of all balls deposited in that node and in its entire subtree.

inputFormat

The input begins with an integer \( n \) indicating 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 \).

Then follow \( n \) lines. The \( i\)-th of these lines contains two integers \( L_i \) and \( R_i \), representing the indices of the left and right children of node \( i \) respectively. If a child does not exist, its value is 0.

It is guaranteed that the tree is a valid rooted binary tree with node 1 as the root.

outputFormat

Output \( n \) space‐separated integers \( r_1, r_2, \dots, r_n \) where \( r_u \) is the number of rounds the game lasts when the target node is \( u \).

sample

2
1 1
2 0
0 0

2 1