概要 N頂点の木が与えられる。各辺に色を付けて塗り分けることを考える。同じ頂点から出ている辺に同じ色がつかないように塗り分けることとしたとき、必要な色の種類の最小値と塗り分けの方法を1つ出力せよ。 制約 2 ≦ N ≦ 10^5 方針 色の種類の最小値は、各…

B - PackDrop 概要 頂点番号が0～N-1である、N頂点の根付き木がある。根は頂点0。また葉がM個あり、i番目の葉の頂点番号をBiとする。 各辺に機器を置いてゆくことを考える。このとき根0から葉Biの間の辺には機器が合計でCi個あるようにし、かつ各辺に置く機…

F - Colorful Tree 概要 N頂点の木が与えられる。辺iは頂点ai, biを結び、色ciがついている。また辺の長さはdiである。 Q個のクエリが与えられる。クエリiではxi, yi, ui, viが与えられ、下記の問いに答えよ。 色xiの辺の長さがyiになったとき、uiからviまで…

E - Virus Tree 2 概要 N頂点の木を下記の要領で塗り分ける。塗り分けにK色まで使えるとき、塗り分けの通り数を求めよ。(mod 10^9 + 7 して出力) 2つの異なる頂点x, yについて、xとyの間の距離が2以下ならxとyは異なる色で塗られる。 制約 1 ≦ N, K ≦ 10^5 …