<span>dp 题解乱写</span>

AGC034E

枚举根节点表示最终汇聚的点。

发现有祖先关系的点对是没必要进行操作的。

关注的是深度的和，不妨把深度为 $x$ ，转化为有 $x$ 个点需要匹配。

只有不同子树的点可以匹配。

如果对于一个点，最大的儿子的大小 $maxsz*2 \leq sumsz$，那么显然可以全部匹配。

否则只要看最大的儿子自身能匹配多少，这个直接不断维护最优策略就完事了。

考虑每个数字的贡献。

每次考虑一个数字。

然后直接数位 dp 记录小于该数字的有 $x$ 个，等于该数字的有 $y$ 个的方案数，复杂度有点高。

发现可以将 $c*w_c$ 这个东西转化为 $w_{x<=c}$，所以可以将 dp 改为小于等于该数字的有多少个。

求出每个串是多少个串的子序列。

考虑构建一个子序列自动机。

就是设 $f_{S,T}$ 表示已经匹配了 $S$，还有 $T$ 在状态里可以匹配一个子序列的方案数。

初始化是 $f_{0,T}$ ，最后要得到的是 $f_{S,0}$。

每次的转移就是选择最靠近的 $0/1$。

因为这在子序列自动机上路径是唯一的，所以这个做法是对的。

首先搞个离散化。

然后对每个点维护一个 $up_i$，表示这个点填的最大的可能的数。

分类讨论可以发现每个 $h_i$ 仅能由 $up_j=h_i$ 的点来满足。

所以对每个出现的权值分别 dp一遍，然后用乘法原理合并就可以了。

显然最优策略中只会出现出现过的权值。

然后考虑搞一个 dp。

因为对于每个人，我们关注最小的权值出现在哪里。

$f_{l,r,x}$ 表示已经处理完了 $[l,r]$ 区间能包含的人的贡献，选择的最小的权值为 $x$。

那么$f_{l,r,x}=\max f_{l,mid-1,p>=x}+f_{mid+1,r,q>=x}+count(l,mid,r)*x$ ，其中 $count(l,x,r)$ 表示包含在区间 $[l,r]$ 并且跨过点 $x$ 的人的个数。

每次取出最低的层数作为根节点，那么划分为的多个儿子是互不干扰的。

所以可以搞一个 dp，用组合数转移就可以了。

dp套dp，处理方法是将内层 dp 的结果记为状态。

发现 $n$ 很小，所以把每一行 dp 都压进状态就可以了。

因为 $dp_{i,j}<=dp_{i,j+1}<=dp_{i,j}+1$，所以状态可以用 $0/1$ 记录，状态数自然不超过 $2^n$。

对于已经确定了每个格子的颜色，可以直接通过dp解决。

所以设 $f_{i,j,C,S}$ 表示到 $i$ 行 $j$ 列，当前轮廓线的状态为$C$，$2^{2^n}$ 的 $dp$ 数组的结果为 $S$的方案数就好了。