Consider the following rooted tree \(T\) that illustrates the process of the teams to be merged.

The rooted tree above corresponds to Sample Input 1.

Each node corresponds to a team at some point during the tournament; especially, each leaf corresponds to (the team consisting only of) a player. We call the node corresponding to team \(A\) simply node \(A\).

Specifically, \(T\) is constructed by the following procedure.

• First, starts with a graph \(T\) with \(N\) nodes \(\lbrace 1 \rbrace, \lbrace 2 \rbrace, \ldots, \lbrace N \rbrace\) and no edges.

• Then, update \(T\) in ascending order of \(i\) as follows, corresponding to each match \(i = 1, 2, \ldots, N-1\):

  • Let \(A\) and \(B\) be the teams involved in match \(i\). Add a node \((A \cup B)\), and let node \(A\) and node \(B\) the children of node \((A \cup B)\).
  • The weight of the edge connecting node \((A \cup B)\) and node \(A\) is set to the probability \(|A|/(|A|+|B|)\) that node \(A\) wins match \(i\); similarly, that between node \((A \cup B)\) and node \(B\) is set to \(|B|/(|A|+|B|)\), the winning rate of team \(B\).

One can use a Disjoint Set Union to simulate the process above, in order to construct a rooted tree \(T\).

By the linearity of expected value, the expected number \(E_i\) of times the team with player \(i\) wins is the sum of the winning probabilities of the team with player \(i\) over all matches that player \(i\) is involved. The matches that player \(i\) is involved correspond to the (proper) ancestors, so \(E_i\) is the sum of the weight of the edges on the path from the root of \(T\) to the leaf \(\lbrace i \rbrace\). Therefore, by performing a depth-first search from the root on \(T\), one can find all of \(E_1, E_2, \ldots, E_N\) in a total of \(O(N)\) time.