(より詳しい解説は後日ブログで公開します)

木が chain だったとすると，頂点を順に見て行って，既に割り振った値の集合と，直前の頂点の値を状態とする DP をすればよいです．

木が star だったとすると，star の中心の値を決めると諸々が決まります．

これらを一般化して，頂点を何らかの順に見て行って，既に割り当てた値の集合と，未確定の頂点と隣接する頂点に割り振った値を状態として DP がしたいです．

「値を同時に覚えておかなければならない頂点数の最大値」の頂点の順番にわたる最小値は，グラフの pathwidth と呼ばれています (より直接的な定義では vertex separation number とも呼ばれています)．頂点の順番を \(O(2^N N)\) 時間の DP で最適化しておくことによって，この問題は \(O(2^N N^{\mathrm{pathwidth} + 1})\) で解けるということになります．

実は \(21\) 頂点以下の木について pathwidth が \(2\) 以下であることが知られているので，制約下で十分高速に動作するように実装できます．一般には，\(k \ge 1\) に対し pathwidth が \(k\) の木の最小頂点数は \((5 \cdot 3^{k-1} - 1) / 2\) です．