ABC 459 E — Select from Subtrees

考察

postorderに処理順を固定すると、頂点iの前に選ばれるのは部分木内の子孫だけで、その個数はT_i−D_iで固定される。部分木の飴総数をS_i、要求総数をT_iとすれば、iの番に残る候補はS_i−T_i+D_i個である。したがってiで選ぶ方法数はC(S_i−T_i+D_i,D_i)となり、各頂点の係数を掛ければよい。S_i<T_iの部分木があれば供給不足なので答えは0。

ただし上側n=S_i−T_i+D_iは大きくても2×10^14程度で、n!を前計算できない。D_iは総和でも10^6以下なので、n(n−1)…(n−D_i+1)にinvfact[D_i]を掛ける。

典型の発動条件

選択順固定による独立化

発動条件: subtree内resourceを祖先・子孫が選び、順序によらず最終条件だけが決まるとき。

postorderに固定して各頂点時点の既消費総数を確定する。

subtree総和と二項係数

発動条件: 各頂点が残resourceから所定数を選ぶ方法数を数えるとき。

供給総和と需要総和の差から候補数を作る。

問題固有の要素

選択結果そのものが後続へ影響して見えても、必要数だけが影響するなら順序を固定して総数へ圧縮できる。

別の問題へ持ち帰る視点: tree上の組合せ積ではsubtree feasibilityと頂点ごとの自由選択数を分離する。

正当性

postorderでは各頂点iより先に選ぶ部分木内の頂点がちょうどT_i−D_i個の飴を使うため、iの選択肢数はS_i−T_i+D_iに固定される。そこからD_i個選ぶ二項係数は子孫の具体的な選び方に依存せず、全頂点の選択を一意に掛け合わせて数える。さらにD_i<Pなので分母D_i!は法の逆元を持ち、falling productとinvfact[D_i]で二項係数を計算できる。

実装上の注意

  • S_i、T_i、上側nは64 bitで保持する。n!は前計算せず、n(n−1)…(n−D_i+1)·invfact[D_i]を計算する。
  • ΣD_i≤10^6<PなのでD_i!は法で可逆。分子の積が法の倍数なら結果0のまま扱う。

復習の核

  • postorderの頂点i直前に何個が必ず消費済みかを小木で追い、具体的subsetによらないことを確認する。

計算量と制約

時間

N 頂点、D=ΣD_i。逆階乗前計算と falling product なら O(N+D)。

空間

木、部分和で O(N)、逆階乗表で O(D)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq P_i \leq N; 1 \leq C_i \leq 10^9; 1 \leq D_i; D_1 + D_2 + \cdots + D_N \leq 10^6; All input values are integers.; T is a rooted tree with vertex 1 as the root.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Select from Subtrees の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 根付き木DP・部分木集約

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 根付き木DP・部分木集約

    補助タグ: 組合せ係数・数え上げ

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 根付き木DP・部分木集約

    • 根付き木で子側の状態を合成し、部分木または木全体の値を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題