入力の木を \(T\) とします．単に「先祖」「子孫」「パス」「部分木」等といったときには，\(T\) におけるものを考えていることとします．

本問題は，\(T\) において先祖・子孫関係にない \(2\) 頂点の間に辺を張ったグラフ \(G\) における最大マッチング問題として定式化可能です．

最大マッチングを Tutte-Berge Formula により求めます．

\(\mathrm{odd}(G-U)-|U|\) が最大となる頂点集合 \(U\) がどのようなものかを考えます．\(S=G-U\) とします．\(\mathrm{odd}(S)+|S|\) が最大となる \(S\) がどのようなものかを考えます．

[1] \(S\) が孤立点のみからなる場合

言い換えれば \(S\) に含まれる任意の \(2\) 点が先祖・子孫の関係になる場合です．\(\mathrm{odd}(S)+|S|\) は，\(S\) が根から最も深い葉までのパス全体と一致する場合に最大となります．

[2] \(S\) が孤立点以外を含む場合

\(G\) において \(a,b\) の間に辺があり，\(T\) において \(\mathrm{LCA}(a,b)=c\) であるとき，辺 \(ab\) が \(c\) を通るということにします．ある辺が通る点のうち深さ最小のものを \(v\) とします．

\(S_1\) を，\(S\) の頂点のうち \(\mathrm{subtree}(v)\setminus\{v\}\) に含まれる点全体とします．このとき次が成り立ちます．

• \(S_1\) は （\(G\) において）連結である．
• \(S-S_1\) は根から \(v\) までのパスに含まれる．

実際，\(G\) の辺 \(ab\) が \(v\) を通るような \(a,b\) をとれば，\(S_1\) の頂点はすべて \(a\) または \(b\) と辺で結ばれています．\(v\) の深さの最小性から，また \(S-S_1\) の頂点が \(a,b\) と辺で結ばれることはないので，後者の性質も分かります．

よって \(v\) を固定したとき，\(\mathrm{odd}(S)+|S|\) の最大値は，\(S\) が次の \(2\) 種の頂点全体からなる場合に実現できます．

• 根から \(v\) までのパス上にある点全体．これらはすべて孤立点（したがって奇数サイズの連結成分）となる．
• \(\mathrm{subtree}(v)\setminus\{v\}\) に含まれる頂点全体．これらはひとつの連結成分となる．

実際，そうではない \(S\) に対して頂点を追加していくことを考えると簡単に証明できます．

[3] 結論

結局，答は各頂点の深さと，部分木サイズだけから Tutte-Berge Formula によって計算できることが分かります．

• 解答例：https://atcoder.jp/contests/arc205/submissions/68826180