選ぶリスの集合を固定したとき，会議の開催地を決める方法として，以下は正当です.

• 木の各辺について，端点のうち，会議の開催地として選んだときのコストが小さい方に向きを付ける. ただし，コストが等しい場合は向きを付けない.
• 頂点 \(1\) を仮の開催地とする. 仮の開催地から有向辺が出ている限り，その辺を辿った先の頂点を仮の開催地とする，ということを繰り返す.
• 最終的な仮の開催地を，会議の開催地に決める.

辺の向きは，その辺を削除したときに分かれる連結成分のうちリスが（真に）多い方に向かいます. ある頂点から有向辺が \(2\) 本以上出ることはありません. そのようなことがあると仮定すると，選ばれたリスのうち過半数を占めるリスの集合として互いに素なものを \(2\) つ以上取れるということになり，矛盾します. また，無向辺の集合は連結です. したがって，上述の方法は，頂点 \(1\) から貪欲かつ単調にコストを改善し，最小コストの頂点で停止します.

したがって，最小コストは，次の和の形に分解できます.

• \((\) 頂点 \(1\) でのコスト \()-\displaystyle\sum_{e}(e\) を辿ったときに改善するコスト \()\)

任意のリスの選び方に対する総和を，各項について計算しましょう.

前者は簡単です. 頂点 \(1\) を会議の開催地としたときのコストの総和は，頂点 \(v\) と頂点 \(1\) の距離を \(d_v\) として \(\sum_{v}2^{N-1}d_v\) です.

後者は各辺について計算します. 根から遠ざかる向きの有向辺 \(u\to v\) について，その辺を取り除いたときの \(u,v\) 側の連結成分で選ばれたリスの数をそれぞれ \(a,b\) とすると，その辺が存在する条件は \(a\lt b\) です. そして，このとき上述の方法において仮の開催地は必ずこの辺を辿り，コストを \(b-a\) だけ改善させます. よって，\(v\) 側の連結成分の大きさを \(s\) とすると，この辺の寄与は

\[ \begin{aligned} &\ \sum_{0\le a\lt b} \binom{s}{b}\binom{N-s}{a}(b-a)\\ &= \sum_{c\ge 1}\sum_{a\ge 0}\binom{s}{a+c}\binom{N-s}{a}c\\ &= \sum_{c\ge 1}c\sum_{a\ge 0}\binom{s}{s-a-c}\binom{N-s}{a}\\ &= \sum_{c\ge 1}c\binom{N}{s-c}\\ &= \sum_{d=0}^{s}(s-d)\binom{N}{d}\\ &= [x^s]\dfrac{x(1+x)^N}{(1-x)^2} \end{aligned} \]

と表されます. 途中で Vandermonde の畳み込みを用いました. この値は \(\binom{N}{i}\) の累積和を \(2\) 回取ることで，すべての \(s\) について計算できます.

結局，以下の解法が従います.

1. 木の根を任意に取る.
2. 根からの各頂点への距離の総和を \(A\) とする.
3. 根以外の部分木について，その大きさを \(s\) としたときの上記の値の総和を \(B\) とする.
4. \(2^{N-1}A-B\) が答えである.

この解法は \(O(N)\) time で動作します.