The provided graph is a tree, so at least one edge must be drawn for all leaves. Let the number of leaves be \(L\). We will distinguish between cases based on the parity of \(L\).

When \(L\) is even

If \(L\) is even, using all leaves once gives a lower bound on the cost. Additionally, all leaves can be matched by the following steps, making \(G\) biconnected.

• Choose a root \(r\) arbitrarily and perform an Euler tour with \(r\) as the root. Label the leaves as \(v_1, v_2, \dots, v_L\) in the order visited in the tour.
• Connect \(v_1\) and \(v_{L/2 + 1}\), \(v_2\) and \(v_{L/2 + 2}\), \(\dots\), \(v_{L/2}\) and \(v_{L}\) with edges.

(Proof sketch) It suffices if the graph remains connected after removing an arbitrary vertex \(v\) from \(G\).
Let \(d\) be the degree of \(v\). Removing \(v\) from \(G\) disconnects \(G\) into \(d\) connected components. Here, due to the nature of Euler tour, there are \(s_1, s_2, \dots s_d\) such that

• \(v_{s_1}, v_{s_1+1}, \dots, v_{s_2-1}\) are in the \(1\)-st connected component
• \(\vdots\)
• \(v_{s_d}, v_{s_d+1}, \dots, v_{s_1-1}\) are in the \(d\)-th connected component.

(Subscripts are considered modulo \(L\).) By combining this fact with \(d \leq 3\), it can be confirmed that the \(d\) connected components will be connected by the newly added edges. (End of proof sketch)

Therefore, this method of spanning edges minimizes the cost.

When \(L\) is odd

Next, let’s consider the case where \(L\) is odd. Let \(v\) denote the \(i\) for which \(W_i\) is the smallest. In this case, using all leaves and \(v\) once gives a lower bound on the cost.

If \(v\) is a leaf, you can arbitrarily choose another leaf \(w\), connect the leaves other than \(w\) in the same way as in the even case, and then connect \(v\) and \(w\).

Now consider the case where \(v\) is not a leaf. The necessary condition for the lower bound above to be achievable is that the following condition is not satisfied.

• For all leaves \(x\), the following holds:
  • For the tree with \(v\) as the root, \(LCA(x, y) = v\) holds for every leaf \(y\) other than \(x\).

(Proof sketch) To achieve the lower bound above, it is necessary to select one leaf \(x\), connect it to \(v\), and biconnect the others in the same way as in the even case.
When the condition holds, no matter which \(x\) is chosen, removing \(v\) from the graph will disconnect \(x\) from the rest.
Conversely, when the condition does not hold, it can be confirmed that it is sufficient to select a vertex pair \((x, y)\) where \(LCA(x, y) \neq v\) and connect them with an edge. (End of proof sketch)

Coupled with the condition \(\deg(v) \leq 3\), the above condition can be intuitively rephrased as follows:

• \(G\) contains exactly three leaves. If we call them \(x, y, z\), then in the rooted tree with \(v\) as the root, \(LCA(x,y) = LCA(y,z) = LCA(z,x) = v\) holds.

Therefore, you can use DFS or similar methods to check the condition and construct a solution (if one exists).

Additionally, if the previous lower bound cannot be achieved, the following can be confirmed:

• The objective is not achievable even if we use (each leaf once) + (the vertex \(v\) multiple times).
• It is achievable if we use (each leaf once) + (the vertex with the second smallest \(W_i\) once).

Thus, it is sufficient to replace \(v\) with the vertex with the second smallest \(W_i\) and proceed with the same discussion.

The computational complexity depends on the implementation, but it is sufficiently fast at about \(\mathrm{O}(N)\) or \(\mathrm{O}(N \log N)\).