T - 独立集合 / Independent Set Editorial by maspy

転置原理を発動します．

クエリ \(i\) の答えを \(ANS_i\) とします．まず適当な \((X_i)\) を入力としたときに \(Y=\sum X_iANS_i\) を求めるアルゴリズムを考えます．このアルゴリズムを転置すれば答が得られます．\((X_i)\) を入力として \(Y\) を求める問題を，以下「転置問題」と呼ぶことにします．

転置問題を解きます．

\(n\) 次多項式 \(f\) について，\(f(p)=[x^n]f_{\mathrm{rev}}(x)\cdot \dfrac{1}{1-px}\) であることに注意します（\(ANS_i\) がこのタイプの値）．

すると，\(Y=\sum X_iANS_i\) は次のような計算結果と解釈できます．各頂点を独立集合に含めるか否かを選ぶ選択方法すべてについて，次の重みの積を足します．

  1. 基本的には，\(v\) を独立集合に入れない場合には重み \(x\)，独立集合に入れる場合には重み \(1\) とする．（\(f_{\mathrm{rev}}\) を考えるということに対応させて，重みを \(1, x\) ではなく \(x, 1\) としている）．
  2. ただし，次のことをちょうど一度行う必要がある．
    • 頂点 \(v\) および，その頂点に来ているクエリ \(i\) をひとつ選ぶ．
    • 頂点 \(v\) を選び，重み \(\dfrac{X_i}{1-q_ix}\) をかける．

そして，最後に \([x^{N-1}]\) をとれば転置問題の答えとなります．

後者の選択を \(0\) 回，\(1\) 回行ったという情報を持たせながら static top tree 上の dp で独立集合を重み付きで数えれば，転置問題が解けます．タイプ 2 の選択を無視すれば，boundary を独立集合に入れるか否かの \(2\times 2\) 個の多項式をクラスタごとに持つことになります．タイプ 2 の選択がある場合には，クラスタごとに \(\prod (1-q_i x)\) を分母とする有理式ということになって，その分子のみを保持するようにすれば，やはり \(2\times 2\) 個の多項式を持つ形になります（合計 \(8\) 個の多項式）．多項式の次数はクラスタ内の頂点数・クエリ数の和に比例します．

これで転置問題が解けるので，そのアルゴリズムを転置すれば \(ANS_i\) を求めるアルゴリズムが得られます．

計算量は，\(n=N+Q\) として \(O(n\log^2n)\) です．

アルゴリズムを転置するパート．

転置問題を解くときに現れる，「\(X_i\) を一度以上選択」したタイプの項 \(z_0,z_1,z_2,\ldots\) に注目します．これらに対する操作 \(z_j(x) := z_j(x) + z_i(x)f(x)\) を列挙しておきます（\(f(x)\) は \(X_i\) を使わず計算される項で，「\(z_j\) に \(z_i\) の定数倍を足す」というタイプの計算です）．

転置をとるときは，最後に行った操作から順に \(Z_i(x) := \mathrm{middle\verb|_|product}(Z_j(x), f(x))\) という計算によってさかのぼっていけばよいです．

posted:
last update: