ABC 401-500/ABC438F - Sum of Mex - 競技プログラミング用 知識集積所

---

問題

ABC438F

必要知識

B以下レベルの内容は省略

• 根付き木※
• 深さ優先探索※または幅優先探索※

考え方

「あるデータの全ての値を合計する」のと「1以上のデータ数+2以上のデータ数+3以上のデータ数+……」は一致する。
この問題では、k以上のデータ数とはすなわちk未満の頂点全てを通る経路数であるため、後者で求める方がよい。

具体的には、以下のようにすればよい。

まず準備として、0を頂点とする根付き木※を作る。
そして、各頂点について、その頂点及びその子孫の頂点数を求めておく。
これは深さ優先探索※または幅優先探索※で可能。

次に、0を通る経路数を求める。
0を途中で通る経路数は、0の異なる子同士の組全てに対し、子孫頂点数の積を求め、それらの合計をとればよい。
これは愚直にやると0に直接つながる子が多い場合にTLEするため、（全ての合計の2乗-全ての2乗の合計）/2で求める。
0を端点とする経路数は単純にn個。

そして最後に、1以上のkについてそれぞれ、k以下を全て通る経路を求める。
これは、以下のように考える。

まず前提として、「ある番号以下の頂点を全て通るための必須経路の、それに含まれる頂点一覧と、両端の頂点番号」を常に保持し、更新していく。
頂点iから、根方向にたどり、必須経路上にある頂点にたどり着くまで進む。
頂点i自体が必須経路上だった場合は特に更新不要。
たどり着いた場所が必須経路の両端だった場合、そっち側の端を頂点iに更新する。
たどり着いた場所が必須経路の途中だった場合、計算を打ち切る。
（i以下を全て通る経路は存在しないので、以後の計算は全て+0にしかならないため）

その後、両端の子孫数の積を取れば、それがi以下の頂点を全て通る経路数である。
ただし、片端が0番だった場合、1番を含む子の分を除外しておく必要がある。
これは、i=1のときに特殊処理を加え、頂点数から該当の子の頂点数を引いておくことで対応できる。

解答例

解答例

注意点

long long型を使う。

答えはint型に収まらない場合がある。

別解