\(T\) のグラフで葉である頂点は、はじめの星においても葉です。また、そのような頂点から \(T\) 上で距離が \(2\) 以下の頂点が同じ星に属します。このことから、以下のアルゴリズムが考えられます。

• \(T\) で葉の頂点を一つ選ぶ。
• 選んだ頂点から距離が \(2\) 以下の頂点の個数（自分含む）を数える。頂点の個数が \(x\) 個のとき、レベル \(x-1\) の星があったことがわかる。
• 数えた頂点および隣接する辺を \(T\) から削除する。

これを、\(T\) の頂点がなくなるまで繰り返すと、答えが得られます。これは適切な実装のもと \(\mathrm{O}(N)\) で動作しますが、些か実装が面倒です。ここでは、簡単な考察のもと実装を楽にする方法を説明します。

以下の補題が成立します。

• 元の星で葉でない頂点を中心とよぶ。\(T\) において、中心同士の距離は必ず \(3\) の倍数であり、中心と葉の距離は必ず \(3\) の倍数ではない。

これは帰納法により示せます。この補題を用いると、以下のアルゴリズムが考えられます。

• \(T\) の中で、元の星で中心であった頂点を一つ選ぶ。これは、\(T\) の葉と結ばれた頂点を選べばよい。
• 選んだ頂点からの最短距離を各頂点について求める。
• 最短距離が \(3\) の倍数であるような各頂点について、その頂点の次数を \(L\) に追加する。

このアルゴリズムは、 bfs または dfs 等により簡単に実装できて、 \(\mathrm{O}(N)\) で動作します。