与えられる木を \(1\) つの頂点を根とした根付き木とみなし，その木上での DP を行います．

最初に描かれる辺を含む頂点の \(1\) つを根とすると，部分木すべてに対して最初に描かれる辺は根の頂点を含むものでなくてはなりません．そうでないとすると，「木を書いている途中で常に辺が連結になっている」という条件を満たさないためです．逆に，この条件さえ満たされていれば，どの順番で辺を描いても条件を満たします．

これは，各部分木に対しても再帰的に言えます．このことから次の DP を考えます：

• \(dp[i] = \) (頂点 \(i\) を根とする部分木を考えたとき，\(i\) を含む辺を最初に描くときの，辺を描く順番の総数)

遷移について考えます．今見ている部分木の頂点を \(i\)，それらの部分木のサイズを \(x_1, x_2, \dots, x_K\) とします（この値は事前に木 DP などで求めておきます）．このとき，部分木内での辺を描く順番は決まっているため，あとは「部分木を選ぶ順番」を決めればよいです．

これは，色 \(1, 2, \dots, K\) の玉がそれぞれ \(x_1, x_2, \dots, x_K\) 個あるときに，同色の玉同士が区別できない場合に横一列に並べる方法の数と等しく，したがって遷移式は

• \(dp[i] = \sum_{c \in C} dp[c] \times \dfrac{(x_1 + x_2 + \dots + x_K)!}{x_1! x_2! \dots x_K!}\)

と表されます（\(C\) は \(i\) の子の頂点集合を表します）

これを，全ての頂点を根として固定した場合について行い，それらについての答えを足し合わせればよいです．ただし，この方法では同じ描き方をダブルカウントしてしまうので，最後に \(2\) で割る必要があります．計算量は \(O(N^2)\) です．