abc152 f

from 競技プログラミングで解法を思いつくための典型的な考え方 abc152_f https://atcoder.jp/contests/abc152/tasks/abc152_f

• N=50
• 木の2点を結ぶパスに1つ以上黒があることが条件
  • 余事象を考える
  • 「パスがすべて白」
  • これは求めやすい、パスの長さをxとしたら2^(N-x)ぐらい
  • 一つの制約に注目して、それが違反してる場合の数は簡単に求まる。制約は複数ある、同時に満たされるケースがダブルカウントされてる→ 包除原理だね
  • 制約は20個ある。2^20はきわどい。DPするのかな？
  • 複数の制約のパスが重なることある？当然ある
    • これは厄介だな？
    • 複数のパスの集合にパスを付け加えた場合の「重なる辺の数」を高速に得ることが必要？
    • 最小共通祖先を前計算する？
• 公式解説
  • 包除原理までOK
  • 複数のパスの重なり合いに関して「最小共通祖先を求めて木上で累積和」らしい、よくわからん
    • 2^20の全パターンでO(N+M)で数えるらしい
• 別解
  • 辺が高々50なのでint64に収まる
  • パスをビットで表現しておけばORで重ね合わせを計算できる