このような問題で、最適ではない(=改善の余地がある)状況を考えることが有効となる場合があります。
今回の場合、 $x_i$ と $y_i$ を結ぶ木上のパスと $x_j$ と $y_j$ を結ぶ木上のパスが頂点を共有しない場合、 $y_i$ と $y_j$ を入れ替えるとよりマッチングの重みが増えます。(証明は略しますが、絵を書いてみると理解しやすいです)

よって、どのパスもある頂点を通るようにしたく、その頂点については以下の条件を満たす必要があることが分かります。

このような頂点はいわゆる重心というものです。ここからは公式解説に合流します。