PKUSC 2024 Day1 t3 独立

想到了一个还比较优美的做法，首先令好 \(dp\) 后设 \(d_{x}=max(dp_{x,0},dp_{x,1})-dp_{x,0}\) 后原问题可以转化为 \(d_{x}=max(w_{x}-\sum_{y\in son_{x}}d_{y},0)\)，最后其实就是求所有方案 \(\sum_{i=1}^{n}d_{i}\) 的和，由于每一个点的期望只与子树有关而与子树外无关，直接对子树外每一个乘 \(m\) 即可，令 \(dp_{x,i}\) 表示 \(d_{x}=i\) 的方案数，据此可以得到一个 \(O(nm^2)\) 的做法。

优化方向是比较明显的，\(m\) 很大，但不难发现 \(dp_{x,i}\) 是一个关于 \(i\) 的低阶多项式，考虑令这个多项式为 \(\sum_{i=0}^{m}a_{i}x^i\)，需要支持的操作是多项式的 \(F(x)=\sum_{y=0}^{x}G(y)H(x-y)\) 与 \(F(x)=G(m-x)\) 操作，至于求 \(\sum_{i=0}^{m}F(i),\sum_{i=0}^{m}iF(i)\) 之类的东西是非常容易的。

直接作普转下下转普是双 \(\log\) 的无法接受，但是我们可以定义不平常的多项式，实验表明 \(a_{0}[x=0]+\sum_{i=1}^{n}a_{i-1}\binom{x}{i}\) 与 \(a_{0}[x=0]+\sum_{i=1}^{n}a_{i-1}\binom{x+i-1}{i-1}\) 都是一种可行的方式，但实际上后者会好一些，由于如果我们定义 \(\binom{0}{-1}=1\) 的话会有 \(\binom{1}{0}\not=\binom{0}{0}+\binom{0}{-1}\) 导致前一个在转移时常数项的部分需要特殊注意，而后者由于都是 \([t^x](\frac{1}{1-t})^i\) 的形式所以无需考虑，而 \(F(x)=\sum_{y=0}^{x}G(y)H(x-y)\) 的操作在这上面就非常容易实现了，就是普通的卷积。

而 \(F(x)=G(m-x)\) 在这上面就稍微复杂一些，但通过复杂推导(暴力用 \(\binom{a}{b}=\binom{-a+b-1}{b}\) 与范德蒙德卷积将组合数展开)后可以发现第一种的系数为 \(\binom{m-i}{m-j}\) 第二种为 \(\binom{m+i}{m+j}\)，所以普通卷积就可以解决，第二种由于规避逆元无需分讨 \(m<n\) 的情况更加方便，可以直接做到 \(O(n^2\log n)\)，仅需一次卷积。

一些多项式前缀和或 \(F(x)=\sum_{y=0}^{x}G(y)H(x-y)\) 的形式的问题令多项式为 \(a_{0}[x=0]+\sum_{i=1}^{m}a_{i}\binom{x+i-1}{i-1}\) 有时更为方便。