\(v\) が葉の場合

1つの色で塗るしかないため、\(S_v = 1\) です。

\(v\) の子が1つだけの場合

\(v\) の子 \(w_1\) を根とする部分木から相異なる2頂点 \(a, b\) を指定したとき、\(\mathrm{lca}(a, b) = v\) となることはありません。 よって、\(v\) をどのような色で塗っても問題の条件の達成には影響を与えません。したがって、\(S_v = S_{w_1}\) です。

\(v\) の子が2つ以上の場合

\(S_{w_i}\) (\(1 \leq i \leq k\)) のうち最大のものを \(S_{1}\) 、2番目に大きいものを \(S_{2}\) とします。

\(S_{1} > S_{2}\) の場合

\(v\) を根とする部分木で少なくとも \(S_{1}\) 色は使う必要があるため、\(S_v \ge S_{1}\) です。

\(S_{1}\) に対応する部分木で使用されている色を \(c_1, c_2, \ldots, c_{S_{1}}\) とします。この時、\(S_{2}\) 以降に対応する部分木を \(c_1, c_2, \ldots, c_{S_{1}-1}\) のみを使って塗り分けて、頂点 \(v\) を \(c_{S_{1}}\) で塗ることで、\(v\) を根とする部分木全体を \(S_{1}\) 色で塗り分けることができます。(下図を参照)

したがって、\(S_v = S_{1}\) となります。

\(S_{1} = S_{2}\) の場合

\(S_{1} > S_{2}\) の場合と同様、\(S_v \ge S_{1}\) です。

ここで、\(S_v = S_{1}\) であると仮定します。このとき、\(S_1\) と \(S_2\) それぞれに対応する部分木を \(T_1, T_2\) とすると、 \(T_1, T_2\) で使用されている色の集合は一致します。（この集合を \(C\) とします。） 頂点 \(v\) の色 \(c_v\) を \(C\) の要素から選んだとき、\(T_1, T_2\) からそれぞれ色 \(c_v\) で塗られた頂点 \(w_1, w_2\) を選ぶことができます。このとき \(\mathrm{lca}(w_1, w_2) = v\) ですが、\(c_{w_1} = c_{w_2} = c_v\) が成り立つため、問題の条件を満たしません。 よって、\(S_v \ge S_1 + 1\) が成り立ちます。

\(S_{1}\) に対応する部分木で使用されている色を \(c_1, c_2, \ldots, c_{S_{1}}\) とします。この時、\(S_{2}\) 以降に対応する部分木を \(c_1, c_2, \ldots, c_{S_{1}}\) のみを使って塗り分けて、頂点 \(v\) をどの頂点でも使われていない色 \(c_{S_{1} + 1}\) で塗ることで、\(v\) を根とする部分木全体を \(S_{1} + 1\) 色で塗り分けることができます。(下図を参照)

したがって、\(S_v = S_{1} + 1\) となります。

これをまとめると、\(S_v = \max(S_{1}, S_{2} + 1)\) が成立します。