公式解説とは異なる構築方法を紹介します． 以下では議論を簡単にするために \(N\geq 3\) を仮定しますが，実装においては \(N=2\) の場合もまとめて処理できます．

与えられた木を \(T\)，葉の個数を \(L\) とし，公式解説と同様に以下の条件を満たす頂点 \(x\) をとります．これは木の重心を求めるアルゴリズムと同様の手順で発見できます．

• \(x\) は \(T\) の葉ではない．
• \(T\) から \(x\) を取り除いてできる各部分木について，その部分木に含まれる \(T\) の葉の個数は \(L/2\) 以下である．

\(T\) の葉の集合を \(S\) とします．このとき \(S\) の要素の並べ替え \((v_1,\dots,v_L)\) であって，以下の条件を満たすものが存在します．

• \(1\leq i\lt L\) を満たす任意の \(i\) について，\(v_i\) と \(v_{i+1}\) は，\(T\) から \(x\) を取り除いてできるグラフにおいて同じ部分木に属さない．

このような列は具体的に以下のように構築できます．

• \(x\) を根とする DFS を行い，葉を訪れた順に取得する．得られた葉を，まず偶数番目（\(v_2,v_4,\dots\)）に前から順に配置し，それがすべて埋まったら奇数番目（\(v_1,v_3,\dots\)）に前から順に配置していく．

以上の準備のもと，以下の手順で条件を満たす valid な塗り方を得ることができます．

1. \(v_{L+1}=x\) とし，\(v_{L+2},\dots,v_N\) を \(S\cup\{x\}\) に含まれない頂点を任意の順で並べた列とする．
2. \(j=1,\dots,K\) について，\(C_j\geq 2\) ならば，\(v_1,\dots,v_N\) のうちまだ色が塗られていない頂点を前から順に最大 \(C_j\) 個まで塗る．
3. まだ色が塗られていない残りの頂点を，使用可能な色を使って塗る（このときの塗り方は任意でよい）．

正当性は以下が成り立つことから従います．

• \(1\leq i\leq L\) について，\(v_i\) と \(v_{i+1}\) 間の単純パスは必ず \(x\) を通る．
• \(v_1\) と \(v_2\) は同じ色で塗られる．また，\(2\leq i\leq L\) について，\(v_{i-1}\) と \(v_i\) の組，または \(v_i\) と \(v_{i+1}\) の組の少なくとも一方は同じ色で塗られる．

実装例(C++) / 実装例(PyPy)