解の上界の導出

あるマッチングにおける，\(T\) の辺 \(i\) の寄与を，そのマッチングのペアのうち辺 \(i\) をまたぐものの個数とします．すると，マッチングの重みは，各辺の寄与の総和と一致します（主客転倒と呼ばれる考え方です）．

この言い換えのもとで，最大マッチングの重みの上界を考えましょう．\(T\) から辺 \(i\) を取り除いたとき，\(T\) は2つの部分木に分かれます．それらの頂点数を \(c_i,N-c_i\) とすると，辺 \(i\) の寄与が \(\min\{c_i,N-c_i\}\) を超えることはありません．よって，マッチングの重みはたかだか \(\displaystyle \sum_{i=1}^{N-1} \min\{c_i,N-c_i\}\) です．

上界を達成する解の構成

この上界を達成するマッチングが存在します．直観的には，木の「真ん中」をまたぐように頂点をマッチさせればよいです（木がパスやスターの場合を考えると思いつきやすいと思います）．

木の「真ん中」に対応する概念に重心というものがあります．木 \(T\) の重心 \(g\) とは，\(T\) から \(g\) を取り除いてできるすべての部分木のサイズが \(\lfloor N/2 \rfloor\) 以下となるような頂点のことです．任意の木について重心は必ず存在し，深さ優先探索により \(O(N)\) 時間で見つけることができます．重心についての解説は以下の記事が参考になります．

• drken 氏による記事：ツリーの重心分解 (木の重心分解) の図解

重心を用いて，上界を達成するマッチングを次のアルゴリズムで構成できます．

1. 木 \(T\) の重心を一つ見つけて \(g\) とする．
2. 木 \(T\) から頂点 \(g\) を取り除いたとき，いくつかの部分木に分かれる．それらを \(T_1,T_2,\dots,T_k\) とする．
3. （\(T_1\) に含まれる頂点の全体），（\(T_2\) に含まれる頂点の全体），…， （\(T_k\) に含まれる頂点の全体）をこの順に連結した配列 \(A\) を作る．
4. \(N\) が偶数ならば \(A\) の末尾に \(g\) を追加する．
5. 各 \(i=1,2,\dots,\lfloor N/2 \rfloor\) について，頂点 \(A_i\) と頂点 \(A_{i+\lfloor N/2 \rfloor}\) をマッチさせる．

正当性の証明

このアルゴリズムで得られるマッチングが上界を達成することを示します．

まず，このマッチングの各ペア \((A_i,A_{i+\lfloor N/2 \rfloor})\) について，\(A_i\) と \(A_{i+\lfloor N/2 \rfloor}\) は異なる部分木に含まれることを示します（\(g\) は部分木 \(T_0\) に含まれるとします）．もしこれらが同じ部分木に含まれるならば， \(A_i,A_{i+1},\dots,A_{i+\lfloor N/2 \rfloor}\) は同じ部分木に含まれるため，この部分木は少なくとも \(\lfloor N/2 \rfloor + 1\) 個の頂点を含むことになります．これは， \(g\) が重心であることに矛盾します．

次に，すべてのペアが異なる部分木に含まれるならば，そのマッチングの重みが上界を達成することを示します．\(T\) を，\(g\) を根とする根付き木とみなします．各辺 \((u_i,v_i)\) （一般性を失わず， \(u_i\) が \(v_i\) の親であるとする）について， \(v_i\) を根とする部分木に含まれるすべての頂点 \(x\) は，あるペア \((x,y)\) に含まれます．\(x,y\) が異なる部分木に属することから，\(x,y\) 間の経路は必ず辺 \(i\) をまたぎます．よって，辺 \(i\) は \(v_i\) の部分木の頂点数だけ重みに寄与します．これは，達成可能な最大の寄与です．

実装例 (PyPy)