「Note」整体DP小记

智慧智慧。

当树上问题能列出二维的 DP 方程，并且转移方程不是很复杂的时候可以用线段树来维护方程，并且用线段树合并来维护。

大概有几种情况可以直接维护。

一种是对于前缀和后缀求和之类的。在线段树合并的过程中实时维护前缀后缀和之类的。

一种是子树加在一起。显然是可以直接维护的。

P5298 [PKUWC2018] Minimax

首先设 \(f_{i,j}\) 表示第 \(i\) 个点的权值为 \(j\) 的概率。

如果一个点是叶子，那么直接设初值。

否则，如果只有一个叶子，那么 \(f_{i,j}\) 直接全都等于这个儿子。

如果有两个儿子，那么假设 \(l,r\) 分别表示左右儿子。那么 \(f_{p,j}=f_{l,j}\times (p_i\times \sum \limits_{k=1}^{j-1} f_{r,k}+(1-p_i)\times \sum \limits_{k=j+1}^m f_{r,k})+f_{r,j}\times (p_i \times \sum \limits_{k=1}^{j-1} f_{l,k}+(1-p_i) \times \sum\limits _{k=j+1}^m f_{l,k})\)

我们可以观察到是 \(l\) 的前缀和乘上一个数加上 \(l\) 的后缀和乘上一个数乘 \(r\) 的单点，\(l\) 的单点乘上另外一边的前缀后缀和。

然后我们可以在两棵线段树合并的时候顺便维护这个东西，维护 \(xl,xr,yl,yr\) 表示左儿子前缀后缀和，右儿子前缀后缀和。然后递归到叶子节点的时候 \(x,y\) 中有一个有值就更新答案。因为权值互不相同所以线段是的叶子节点只有一边可能有值。

最后在根节点维护答案即可。

Submission

P6773 [NOI2020] 命运

喵喵题

状态也不好想。

状态是 \(f_{u,i}\) 表示假设 \(u\) 的子树之外已经确定了，从 \(u\) 向祖宗找，只考虑下面的点在子树里，上面的点在子树外，最近的没有被满足的点的深度为 \(i\) 的方案数。

那么考虑转移。考虑将 \(v\) 子树合并到 \(u\) 子树上。那么就考虑 \(u-v\) 这条边的权值。如果这条边是重要的，那么只有可能是原来 \(u\) 子树上的限制导致的未满足。否则就是两个子树未满足的限制是最大值。

\(f_{u,i}=\sum\limits_{j=0}^{dep-1} f_{u,i}f_{v,j}+\sum \limits_{j=0}^i f_{u,i}f_{v,j}+\sum \limits_{j=0}^{i-1} f_{u,j}f_{v,i}\)

然后还是考虑在线段树合并的时候维护这些。第一项需要 \(v\) 子树的和，在线段树合并之前算出来即可。第二项和第三项需要在边递归的过程中边计算贡献，到叶子节点的时候需要增加贡献。

Submission

P4365 [九省联考 2018] 秘密袭击 coat

题意：树上所有联通块中第 \(K\) 大的点权之和。如果不足 \(K\) 个数，算成 \(0\)。

sol：首先是我想要学会的 trick

\(ans=\sum\limits_{S\sube T} kth\)

\(=\sum \limits_{i=1}^W i \sum\limits_{S\sube T} [kth =i]\)

\(=\sum\limits_{i=1}^W \sum \limits_{S\sube T} [kth\geq i]\)

这一步不是很好理解

\(\sum\limits_{i=1}^W \sum \limits_{S\sube T} [kth\geq i]\)

\(=\sum\limits_{i=1}^W\sum \limits_{S\sube T} \sum \limits_{j=i}^n [kth=j]\)

这样对于每一个 \(j\)，如果 \(j=1\)，只会被计算一次，\(j=2\)，只会被计算 \(2\) 次，以此类推，就相当于在和式前面乘 \(i\)。

\(=\sum\limits_{i=1}^W \sum \limits_{S\sube T} [cnt_i\geq k]\)，\(cnt_i\) 指集合中大于等于 \(i\) 的数出现次数。

然后设 DP 方程 \(f_{i,j,k}\) 表示 \(i\) 为根的子树，\(cnt_j\) 为 \(k\) 时的方案数。

显著的，这是一个背包。

但是背包直接转移时 \(O(n^2W)\) 的。

我们考虑将背包写成生成函数的形式 \(F_{i,j}(X)=\sum f_{i,j,k} X^k\)

这样 \(F_{i,j}(X)=X^{j\leq val_i}\prod (F_{v,j}(X)+1)\)

最终答案就是 \(\sum\limits_{i=1}^n \sum \limits_{j=1}^W \sum\limits_{l=k}^n [x^l] F_{i,j}(x)\)

我们假设 \(G_{i,j}(x)=\sum \limits_{v\in sub_i} F_{v,j}(x)\)

容易得到 $G_{i,j}(x)=\sum $