考えたこと

考察するまでもなく自明な気がするが、言語化しないとだな

ツリーだから合流はなく、つまり親から色Xの辺でやってきた頂点はXを除いた色で塗ればいい、それによって矛盾が発生することはない

必要な最小色数は頂点の最大位数

適当な頂点を根として塗っていけば良い

公式解説

その通り