MST on Tree

まずある頂点を根とした最小有向全域木の重みは $O(N)$ 時間で求めることができます。

次に隣接する頂点 $u, v$ を根とする最小有向全域木は、$u, v$ を結ぶ辺のみが変わります。 したがって、隣接する頂点を根とする最小有向全域木の重みは、$O(1)$ 時間で求めることができます。

以上より、一つの頂点を適当に選び最小有向全域木の重みを求め、 最小有向全域木の重みを管理しながら DFS などで全ての頂点について答えを求めることで、全体で $O(N)$ 時間が達成できます。