試合によって \(2\) つのチームが併合されていく過程を表す下図のような根付き木 \(T\) を考えます。

上の図は入力例１に対応する根付き木です。

各ノードは大会中のある時点でのあるチームに対応し、特に、葉は各プレイヤー（そのプレイヤー \(1\) 人のみからなるチーム）に対応します。 チーム \(A\) に対応するノードを以下では単にノード \(A\) と呼びます。

より具体的には、\(T\) は下記の手順でつくられます。

• まず、大会開始時の状態の再現として、\(N\) 個のノード \(\lbrace 1 \rbrace, \lbrace 2 \rbrace, \ldots, \lbrace N \rbrace\) のみからなる辺を持たないグラフ \(T\) からはじめます。

• その後、各試合 \(i = 1, 2, \ldots, N-1\) の進行に対応して、\(i\) の昇順に下記の通りに \(T\) を更新します。

  • 試合 \(i\) で対戦するチームを \(A\) と \(B\) とする。ノード \((A \cup B)\) を新たに追加し、ノード \(A\) とノード \(B\) をノード \((A \cup B)\) の子とする。
  • ノード \((A \cup B)\) とノード \(A\)を 結ぶ辺の重みを、試合 \(i\) におけるチーム \(A\) の勝率 \(|A|/(|A|+|B|)\) とし、同様に、ノード \((A \cup B)\) とノード \(B\) を結ぶ辺の重みを、試合 \(i\) におけるチーム \(B\) の勝率 \(|B|/(|A|+|B|)\)と する。

UnionFind を用いて上記の手順をシミュレーションすることで、根付き木 \(T\) が構築できます。

プレイヤー \(i\) が所属するチームが勝つ回数の期待値 \(E_i\) は、期待値の線形性から、プレイヤー \(i\) が参加する試合全てにわたる「プレイヤー \(i\) が所属するチームの勝率」の総和です。 プレイヤー \(i\) が参加する各試合は、\(T\) 上では葉 \(\lbrace i \rbrace\) の各（真の）祖先に対応するので、\(E_i\) は \(T\) の根から葉 \(\lbrace i \rbrace\) までのパス上の辺の重みの総和です。 したがって、\(T\) 上で根から深さ優先探索等を行うことで、\(E_1, E_2, \ldots, E_N\) をまとめて \(O(N)\) 時間で求めることができます。