ABC160 - F - Distributing Integers
概要
サイズNの木が与えられる。頂点に1~Nの番号が振られている。k=[1, N]として次の条件下で問題を解け。
- 頂点kに最初に赤色を塗る。次に塗ることができるのは、すでに塗った頂点に隣接する頂点、というルールのもとで色を塗るとき、何通りの塗り方が存在するか？
非常に大きくなることがあるので、で割ったあまりを答えよ。
制約： 1 <= N <= 2 * 10^5
ACするまで
1. すべての頂点について求める木の問題、全方位木DPでは？
2. ひとまず頂点1についての問題を解いてみる。
3. 何通りになるかは、「それぞれの子供の場合の数」と「それぞれの子供のサイズ」が関与してそう。
4. 時間内で思いつかなかった。
5. 同じものを含む順列の考えを使おう！
6. バグらせずに全方位木DPをやって、AC!
考察
根が1と固定されてる時の場合の数を数え上げてみることを考える。
ひとまず、シンプルに
dp[i] := 根が1とみなした木のもとで、頂点iを根とした部分木内での埋め方の場合の数
と定めて、更新できるのか？をかんがえる。
全方位木DPは、
ei1333.hateblo.jp
が分かりやすいと思う。
ACソースコード：
Submission #11322834 - AtCoder Beginner Contest 160
一言
惜しい。この悔しい思いをあと何回すればいいのか
