CS Academy Round 51 - Tree Coloring
ツリーと色数kが与えられる。この時、あるノードに対して、そのノードから距離1のノードと、距離2のノード両方と色が異なるように頂点を彩色したい。彩色の仕方は何通りあるか。
あるノードに着目する時、距離1または距離2のノードがすべて異なるということなので、そのノードの隣接ノードの集合を考える。するとその隣接ノード＋今見ているノードの集合について、これらは全て距離2以下であるため、その集合の数をmと置くと彩色数は k * (k - 1) * .. * (k - m + 1) となる。ここから次の隣接ノードに移る。すると、同じように考えられるが、既にカウント済みのノードがあるため、そのカウント済みのノードをlとおくと、それらのノードの色は既にカウント済みであり、かつ全て色が異なる。したがって今見ている集合の彩色数は (k - l) * (k - l - 1) * .. * (k - m + 1) となる。
これらをdfsで辿っていき、子ノードの彩色数の積に今見ているノードの彩色数の積、という値を返してどんどん根まで計算すると答え。O(N)。
