頂点 \(1\) を根とする根付き木で考える.

頂点 \(i\) とその親の辺を結ぶ辺が利用される回数は頂点 \(i\) を根とする部分木に含まれる頂点数を \(p_i\) とすると, \(2 p_i (N - p_i)\) となる. これに辺の長さを掛けたものの総和を取る.