与えられるグラフは木なので、少なくとも全ての葉に 1 本以上の辺を張る必要があります。葉の枚数を \(L\) として、\(L\) の偶奇で場合分けします。

\(L\) が偶数のとき

\(L\) が偶数の場合、全ての葉を 1 回ずつ使用するのがコストの下界になります。 そして、次の手順で全ての葉をマッチングすると \(G\) を二重頂点連結にできます。

• 根 \(r\) を適当に決めて、\(r\) を根としてオイラーツアーをする。葉に対してオイラーツアーでの訪問順に \(v_1, v_2, \dots, v_L\) とラベルを貼る。
• \(v_1\) と \(v_{L/2 + 1}\), \(v_2\) と \(v_{L/2 + 2}\), \(\dots\) \(v_{L/2}\) と \(v_{L}\) を辺で結ぶ。

(略証) 辺を追加したあとのグラフを \(G'\) とする。\(G'\) から頂点 \(v\) を自由に選んで取り除いたあとのグラフが連結であればよい。
\(v\) の次数を \(d\) とする。\(G\) から \(v\) を取り除くと \(d\) 個の連結成分に分かれる。ここでオイラーツアーの性質から, ある \(s_1, s_2, \dots s_d\) が存在して

• \(v_{s_1}, v_{s_1+1}, \dots, v_{s_2-1}\) が \(1\) 番目の連結成分に含まれる
• \(\vdots\)
• \(v_{s_d}, v_{s_d+1}, \dots, v_{s_1-1}\) が \(d\) 番目の連結成分に含まれる

という関係になることが確認できる。 (添え字は \(\bmod L\) とする。) この事実と \(d \leq 3\) であることを合わせると、新たに追加した辺によって \(d\) 個の連結成分が連結になることが確認できる。(略証終わり)

よって、このような辺の張り方がコストを最小化します。

\(L\) が奇数のとき

次に、\(L\) が奇数の場合を考えます。\(W_i\) が最小である \(i\) を \(v\) とします。このとき、(全ての葉 + \(v\)) を 1 回ずつ使用するのがコストの下界になります。

\(v\) が葉である場合は、\(v\) 以外の葉 \(w\) を適当に取って、\(w\) を除く葉について偶数と同様に結んだあとに \(v\) と \(w\) を結べばよいです。

\(v\) が葉でない場合を考えます。上に書いた下界が達成できる必要条件は次の条件が成り立たないことです。

• すべての葉 \(x\) について次の条件が成り立つ。
  • \(v\) を根とする根付き木について、\(x\) 以外の任意の葉 \(y\) について \(LCA(x, y) = v\) が成り立つ。

(略証) 先の下界を達成するには、葉 \(x\) を 1 枚選んで \(v\) と結び、それ以外を偶数と同様の要領で二重頂点連結にすることが必要である。
条件が成り立つ時、どのように \(x\) を選んでも、 \(v\) をグラフから取り除くと \(x\) とそれ以外の部分が分断されてしまう。
逆に条件が成り立たない場合、\(LCA(x, y) \neq v\) である頂点対 \((x, y)\) を選んで辺を張ればよいことが確認できる。(略証終わり)

\(\deg(v) \leq 3\) という条件も合わせると、上の条件は次のような直感的な表現に言い換えられます。

• \(G\) はちょうど 3 枚の葉を含む。葉を \(x, y, z\) と呼ぶと、\(v\) を根とする根付き木について \(LCA(x,y) = LCA(y,z) = LCA(z,x) = v\) が成り立つ。

よって DFS などを用いることで、条件の確認や(解が存在する場合の)解の構成ができます。

また、先の下界を達成できない場合は、

• (葉を 1 回ずつ) + (\(v\) を複数回) でも達成できないこと
• (葉を 1 回ずつ) + (\(W_i\) が 2 番目に小さい点を 1 回) で達成できること

が確認できるので、\(v\) を \(W_i\) が 2 番目に小さい点に置き換えて同様の議論をやればよいです。

計算量は実装にもよりますが \(\mathrm{O}(N)\) や \(\mathrm{O}(N \log N)\) 程度で、十分高速です。