一大堆错，别喷了。

前言

下图取自某人的 PPT，有删改。

题面

APIO2014 序列分割

题目大意

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏，第 $i$ 个位置的值为 $a_i$。

这个游戏中你需要把序列分成 $k + 1$ 个非空的块，为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：

• 选择一个有超过一个元素的块（初始时你只有一块，即整个序列）。

• 选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数，你想要最大化最后的总得分。

数据范围

$2 \le n \le 10^5$，$1 \le k \le \min\{n - 1, 200\}$。

闲话：pjt 问我 T1 是什么，我说是动态规划板子，这很合理。

CF1517G Starry Night Camping

题目大意

有 $n$ 顶帐篷，第 $i$个帐篷位于点 $(x_i, y_i)$ 上，权值为 $w_i$。当且仅当 $x_i$ 和 $y_i$ 都是偶数时，帐篷 $i$ 才是重要的。

移除一些帐篷，使得对于每个剩余的重要帐篷 $(x, y)$，不存在另外 $3$ 个帐篷 $(x' _ 1, y' _ 1),(x' _ 2, y' _ 2)$ 和 $(x' _ 3, y' _ 3)$，使得以下两个条件都成立：

• $|x'_j-x|,|y'_j-y|\le 1$，对于所有 $j\in\{1,2,3\}$。

• 这四个帐篷形成一个平行四边形（或矩形），它的一条边平行于 $x$ 轴。

将未移走的帐篷权值之和最大化，输出最大值。

数据范围

$1\le n\le 1000$，$-10^9\le x_i,y_i\le 10^9$，$1\le w_i\le 10^9$。

CF1983E I Love Balls

题目大意

Alice 和 Bob 在玩游戏。他们面前有 $n$ 个球，第 $i$ 个球的价值为 $v_i$，且前 $k$ 个球为“特殊球”，Alice 为先手。

每一轮，Alice 或 Bob 会随机从剩余的球中选取一个球并把它取出，获得它的价值。

如果这个球为特殊球，则下一轮的玩家不变，否则下一轮的玩家改变。

问 Alice 和 Bob 各自得到的价值的期望对 $10^9 + 7$ 取模的值。

数据范围

多测，$1\le T\le 2\times 10^5$，$1\le k\le n\le 4\times 10^5$，$1\le v_i\le 10^7$。

CEOI2017 Building Bridges

有 $n$ 根柱子依次排列，每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。

现在想要建造若干座桥，如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间，那么需要 $(h_i-h_j)^2$ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$，注意 $w_i$ 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

数据范围

$2\le n\le 10^5$，$0\le h_i,\vert w_i\vert\le 10^6$。

CF1278F Cards 加强

题目大意

有 $m$ 张牌，其中一张是王牌。

现在你执行 $n$ 次右侧操作：洗牌后查看第一张牌是什么。

令 $x$ 为洗牌后第一张牌为王牌的次数，现在假设洗牌时 $m!$ 种牌的排列出现的概率均相等，求 $x^k$ 的期望值，答案对 $998244353$ 取模。

数据范围

$1\le n,m\le 998244353$，$1\le k\le 10^7$。

闲话：本来的范围 $k\le 5000$。

gym 102331 J Jiry Matchings

题目大意

给定一棵树 $n$ 个节点的有边权的树，求对于 $k\in[1,n]\cap\mathbb{Z}$ 的大小为 $k$ 的匹配的最大权值。

一个图的匹配就是在一张图上选择一些边，要求这些边没有公共的端点。

数据范围

$1\le n\le 2\times 10^5$，时限 $2s$。

solution

APIO2014 序列分割

容易得到一个性质：

同样的切法得到的答案都是一样的，换而言之切的顺序与答案无关。

容易证明，设我们把三段和为 $D,C,Z$ 的三段切开，那么：

• 先切 $C,Z$ 的贡献为：$(D+C)\times Z+D\times C$，也就是 $DC+DZ+CZ$。
• 先切 $D,C$ 的贡献为：$D\times (C+Z)+C\times Z$，也就是 $DC+DZ+CZ$。

设 $s_i=\sum\limits_{i=1}^i a_i$，$F_{i,j}$ 表示前 $i$ 次切割 $j$ 次可以得到的贡献的最大值，注意这个的状态数是 $O(nk)$ 的如果 $O(1)$ 转移是可以通过的。

我们记 $f_k=F_{i,k}$，$g_k=F_{i-1,k}$，那么显然有转移方程：

$f_i=\max\{g_j+s_j\times (s_i-s_j)\}$

显然添加的第 $[i,j]$ 段会和前面所有的段都发生贡献，所以需要乘以 $s_j$。

观察，Z_drj 都可以看出来可以斜率优化。

我们取任意的 ${j1}\lt {j2}$ 且满足 $f_i$ 的决策点是 ${j2}$ 优于 ${j1}$，那么就可以得到下面的不等式：

$g_{j2}+s_{j2}\times (s_i-s_{j2})\gt g_{{j1}}+s_{{j1}}\times (s_i-s_{j1})$

整理一下得到：

$(s_i\times s_{j2})+(g_{{j2}}-{s_{{j2}}}^2)\gt (s_i\times s_{j1})+(g_{{j1}}-{s_{{j1}}}^2)$

移项：

$s_i\times (s_{j2}-s_{j1})\gt g_{{j1}}-{s_{{j1}}}^2-g_{{j2}}+{s_{{j2}}}^2$

因为 $s_{j2}\gt s_{j1}$，所以有：

$-s_i\lt \dfrac{(g_{{j2}}+{s_{{j2}}}^2)-(g_{{j1}}-{s_{{j1}}}^2)}{s_{j2}-s_{j1}}$

总结一下，如果上面的式子成立那么 $j2$ 比 $j1$ 要优。

考虑建立一个直角坐标系，把 $s$ 作为 $X$ 坐标，把 $g+s^2$ 作为 $Y$ 坐标，那么每一个决策就都成为了一个点。

假设有三个决策点 $D,C,Z$，他们的斜率分别是 $k_1$ 和 $k_2$，且 $k_0$ 是 $-s_i$，满足下图：

那么根据我们上面得到的式子有：

• 如果 $k_0<k_1$，那么 $C$ 比 $D$ 优。
• 如果 $k_0<k_2$，那么 $Z$ 比 $C$ 优。
• 观察得到 $k_1<k_2$，即上图是一个下凸。

那么有三种情况：

• $k_0<k_1<k_2$，那么 $Z$ 比 $C$，$D$ 优。
• $k_1<k_0<k_2$，那么 $D$，$Z$ 比 $C$ 优。
• $k_1<k_2<k_0$，那么 $D$ 比 $C$，$Z$ 优。

发现 $C$ 太逊了，也就是在这个情况下是决策点永远不可能是下凸。

因为永远不可能是下凸，所以肯定是上凸（好像这句话是废话）。

显然，如果决策点 $k$ 被选择，当且仅当这个点前面的斜率都比 $k_0$ 小，它后面的点都比他大。

所以瞪眼法可以得到如果蓝线是 $k_0$ 那么 $D$ 就是决策点。

考虑这个东西怎么维护，发现新加入的点的斜率都是 $X$ 坐标都是单调的，那么显然可以直接维护一个可以在末尾添加元素的玩意。

因为上凸包的斜率具有单调性，且寻找的是第一个大于的点，所以可以二分查找，转移的时间复杂度是 $O(\log n)$ 的。

但是发现这个题目的 $k_0$ 也是递增的，所以其实比 $k_0$ 小的以后都不会取到，所以可以直接在末尾弹出元素。

所以最后的时间复杂度为 $O(nk)$，就是一个斜率优化的板子，让某些人复习或者预习一下。

CF1517G Starry Night Camping

将节点的 $x_i,y_i$ 的奇偶性划分成 $A,B,C,D$ 四个集合，注意相邻集合在图中需要时可以满足 $\operatorname{dist}$ 为 $1$ 的。

容易发现对于一个不合法的四边形，一定满足四个帐篷之间的切比雪夫距离均为 $1$ 而且四个点分别属于 $A,B,C,D$ 四个集合。

每一种帐篷只有选择或者不选择，考虑使用最小割进行求解。

因为帐篷 $u$ 无法在最小割中被删除，考虑将 $u$ 拆为两个节点 $u_1,u_2$ 并用权值为 $w_u$ 的边链接 $u_1,u_2$，如果将边 $u_1\to u_2$ 删除，那么就意味着帐篷 $u$ 被放弃掉了。

考虑将集合编号相邻且在图上曼哈顿距离为 $1$ 的节点之间连边，具体的要将编号小的 $x_2$ 向集合编号较大的 $y_1$ 连边边权为 $inf$ 的边。

最后将 $A$ 集合内的所有点与 $S$ 连边，将 $D$ 集合内所有的点与 $T$ 连边，边权都是 $inf$。

显然，如果节点 $a,b,c,d$ 是不合法的帐篷，那么它们显然会被边权为 $inf$ 的边全部连接起来，那么只有割掉任意一条边权不为 $inf$ 的边才可以使 $S,T$ 不连通。根据上面的解释，这也就是放弃了一个帐篷。

时间复杂度为 $O(n^3)$，但是是网络流。

CF1983E I Love Balls

定义一般球被 Alice 拿出的期望次数和平均值分别为 $p_1,s_1$，特殊球为 $p_2,s_2$，那么显然 Alice 拿出的球的期望为 $p_1s_1+p_2s_2$。

因为 Alice 和 Bob 会等概率的拿球，所以 $s_1,s_2$ 就是一般球与特殊球权职和的平均。

考虑没有特殊球的情况，如果将普通球排成一列两个玩家一次取出，显然这样的期望值与题目描述的一样。

但是题目插入了 $k$ 个特殊球，可以理解为将原本的序列分成的几段，每一段只有在最后包含了一个普通球或者不包含，每一个玩家一次取出一段。

发现插入特殊球并没有影响玩家取出普通球的个数，可以得到 $p_1=\lfloor \dfrac{n-k+1}{2}\rfloor$。

显然 Alice 遇到的缝隙的数量是 $\lfloor \dfrac{n-k+2}{2}\rfloor$，每一个缝隙中遇到的球的期望是 $\dfrac{k}{n-k+1}$，所以 $p_2=\dfrac{k\cdot \lfloor \dfrac{n-k+2}{2}\rfloor}{n-k+1}$。

CEOI2017 Building Bridges

设 $s_i=\sum\limits_{j=1}^i w_i$，考虑前 $i$ 个柱子并且保留第 $i$ 个柱子的最小代价。

那么有容易想到朴素的转移方程：

$f_{i}=\min\{f_j+s_{i-1}-s_j+(h_i-h_j)^2\}$

考虑把这个玩意展开，得到：

$f_j+s_{i-1}-s_j+{h_i}^2+{h_j}^2-2\times h_ih_j$

发现出现了乘积项，考虑使用斜率优化。

注意，因为 $w_i$ 有负数所以 $h_i$ 不再递增了。

考虑如果 $h$ 递增，那么下面的分析会假设 $j1<j2$ 以得到 $h_{j1}<h_{j2}$ 来移项，但是实际上我们并没有直接的使用 $j1$ 和 $j2$ 之间的大小关系。

所以我们可以换一种假设方式，假设 $h_{j1}<h_{j2}$ 且 $j2$ 比 $j1$ 优。

套路的可以得到不等式：

$(-2\times h_ih_{j1})+(f_{j1}-s_{j1}+{h_{j1}}^2)+(s_{i-1}+{h_i}^2)>(-2\times h_ih_{j2})+(f_{j2}-s_{j2}+{h_{j2}}^2)+(s_{i-1}+{h_i}^2)$

移项得到：

$2h_i\times (h_{j2}-h_{j1})>(f_{j2}-s_{j2}+{h_{j2}}^2)-(f_{j1}-s_{j1}+{h_{j1}}^2)$

因为有 $h_{j1}<h_{j2}$，所以如果按照 $h$ 排序之后满足下式就可以得到 $j2$ 比 $j1$ 优：

$2h_i>\dfrac{(f_{j2}-s_{j2}+{h_{j2}}^2)-(f_{j1}-s_{j1}+{h_{j1}}^2)}{(h_{j2}-h_{j1})}$

容易发现应该维护下凸壳，考虑让强行让 $h$ 单调。

考虑分治，先处理左区间，然后再用左区间得到的结果处理右区间。

具体的，把左右区间分别递归完之后再归并排序即可，时间复杂度为 $O(n\log n)$。

另外有人发现这是 CDQ 分治吗？

CF1278F Cards 加强

定义 $f_i$ 表示有将 $i$ 个不同的元素组成的特定结构的方案数，$g_i$ 表示从 $i$ 个元素任意选出一些（可以不选）组成特定结构的方案数。

对于知道 $f_i$ 或者 $g_i$ 中的任意一个就可求解另外一个，其公式如下：

$g_n=\sum\limits_{i=0}^n{n\choose i}f_i$

$f_{n}=\sum\limits_{i=0}^n{n\choose i}(-1)^{n-i}g_i$

就是容斥，直接感性理解，相信 ljw 在讲组合数的时候会讲的。

发现有人不会斯特林数，$\begin{Bmatrix}n\\ k\end{Bmatrix}$ 表示把 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。

简单讲一下怎么求通项公式：

设 $G_i$ 表示将 $n$ 个不同元素放入 $i$ 个不同盒子允许为空的方案数，$F_i$ 表示将 $n$ 个不同的元素放入 $i$ 个不同盒子不允许为空的方式。

那么显然：

$G_i=i^n$

同时还有：

$G_i=\sum\limits_{j=0}^i {i\choose j} F_j$

发现上面的式子和二项式反演一样，所以得到：

$F_i=\sum\limits_{j=0}^i (-1)^{i-j}\times {i\choose j}\times G_i$

将 $G$ 带入并化简得到：

$F_i=\sum\limits_{j=0}^i\dfrac{(-1)^{i-j}\times i!\times i^n}{j!\times (i-j)!}$

因为斯特林数的盒子不一样，所以 $F_k$ 就是就是 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ 的 $k!$ 倍，所以得到：

$\begin{Bmatrix}n\\ k\end{Bmatrix}=\dfrac{F_k}{k!}=\sum\limits_{i=0}^k\dfrac{(-1)^{k-i}\times i^n}{i!\times (k-i)!}$

得到：

$i^n=\sum\limits_{j=0}^i j!\times {i\choose j}\times \begin{Bmatrix} n\\j\end{Bmatrix}$

把组合数展开然后约分得到：

$i^n=\sum\limits_{j=1}^i \dfrac{i!}{(i-j)!}\times \begin{Bmatrix} n\\j\end{Bmatrix}$

记抽出王牌的概率 $\dfrac{1}{m}$ 为 $p$，那么按照题目的要求写出式子：

$\sum\limits_{i=0}^n{n\choose i}p^i(1-p)^{n-i}i^k$

把 $i^k$ 根据套路写成第二类斯特林数的形式：

$\sum\limits_{i=0}^n {n\choose i}p^i(1-p)^{n-i}\sum\limits_{k=0}^{j}\begin{Bmatrix}k\\ j\end{Bmatrix}i^{\underline{j}}$

其中 $i^{\underline{j}}$ 表示 $\dfrac{i!}{(i-j)!}$，oi-wiki 里面总计了一些常用的符号。

因为 $n$ 太大了不可以接受，所以考虑把里面的循环提到外面去。

$\sum\limits_{j=0}^k \begin{Bmatrix}k\\ j\end{Bmatrix}\sum\limits_{i=0}^n{n\choose i}i^{\underline{j}}p^i(1-p)^{n-i}$

展开得到：

$\sum\limits_{j=0}^k\begin{Bmatrix}k\\ j\end{Bmatrix}\sum\limits_{i=1}^n\dfrac{i!}{(i-j)!}\dfrac{n!}{i!(n-i)!}p^i(1-p)^{n-i}$

那么合理组合得到：

$\sum\limits_{j=0}^k\begin{Bmatrix}k\\ j\end{Bmatrix}\sum\limits_{i=1}^n\dfrac{(n-j)!}{(i-j)!\times (n-i)!}\times \dfrac{n!}{(n-j)!}\times p^i(1-p)^{n-i}$

考虑组合意义得到：

$\sum\limits_{j=0}^k\begin{Bmatrix}k\\ j\end{Bmatrix}n^{\underline j}\sum\limits_{i=1}^n{n-j\choose i-j}p^i(1-p)^{n-i}$

发现上面的组合数太丑陋了，把 $i-j$ 替换为 $i$ 得到：

$\sum\limits_{j=0}^k\begin{Bmatrix}k\\ j\end{Bmatrix}n^{\underline j}\sum\limits_{i=0}^{n-j}{n-j\choose i}p^{i-j}(1-p)^{n-(i-j)}$

观察式子发现和二项式定理很像：

$(a+b)^n=\sum\limits_{i=0}^n {n\choose i}a^{i}b^{n-i}$

把 $p^i$ 提出来，带入上式得到：

$\sum\limits_{j=0}^k \begin{Bmatrix}k\\ j\end{Bmatrix}n^{\underline j}p^j (p+1-p)^{n-i}$

也就是：

$\sum\limits_{j=0}^k \begin{Bmatrix}k\\ j\end{Bmatrix}\dfrac{n!}{(n-j)!}p^j$

这时可以 $O(k^2)$ 朴素求解斯特林数，也可以只用卷积做到 $O(k\log k)$ 求解，但是还是无法做到线性求解。

把通项公式带入上式：

$\sum_{i=0}^k\dfrac{n^{\underline{i}}p^i}{i!}\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}j^k$

交换求和的顺序：

$\sum_{j=0}^k(-1)^{j}j^k\sum_{i=j}^k\dfrac{n^{\underline{i}}(-p)^i}{i!}\binom{i}{j}$

展开组合数：

$\sum\limits_{j=0}^k(-1)^jj^k\sum\limits_{i=j}^k \dfrac{n^{\underline{i}}(-p)^i}{i!}\times \dfrac{i!}{j!(i-j)!}$

整理一下：

$\sum_{j=0}^k\dfrac{(-1)^{j}j^k}{j!}\sum_{i=j}^k\dfrac{n^{\underline{i}}(-p)^i}{(i-j)!}$

和上面的套路同样的，把 $i$ 替换为 $i+j$ 得到：

$\sum\limits_{j=0}^k\dfrac{(-1)^jj^k}{j!}\sum\limits_{i=0}^{k-j}\dfrac{n^{\underline{i+j}}(-p)^{i+j}}{i!}$

整理一下得到：

$\sum_{j=0}^k\dfrac{(-1)^{j}j^k(-p)^j}{j!}\sum_{i=0}^{k-j}\dfrac{n^{\underline{i+j}}(-p)^i}{i!}$

继续变形得到：

$\sum_{j=0}^k\dfrac{j^kp^jn!}{j!(n-j)!}\sum_{i=0}^{k-j}\dfrac{(n-j)!}{i!(n-i-j)!}\times (-p)^i$

考虑组合意义得到：

$\sum\limits_{j=0}^k\dfrac{j^kp^jn^{\underline j}}{j!}\sum\limits_{i=0}^{k-j}{n-j\choose i}(-p)^i$

观察上式的第二个 $\sigma$ 的前面，发现：

• 阶乘和下降阶乘幂显然可以 $O(k)$ 预处理。
• $g(x)=p^x$ 显然可以 $O(k)$ 预处理。
• $g'(x)=x^k$ 是积性函数，可以通过欧拉筛 $O(k)$ 预处理。

所以我们只需要在 $O(k)$ 或者更低的时间复杂度内求解出后面的玩意就可以了。

考虑设函数：

$f(j)=\sum_{i=0}^{k-j}\binom{n-j}{i}p^i$

那么容易想到可以去递推求解，那么直接考虑两式的差：

$\sum_{i=0}^{k-j+1}\binom{n-j+1}{i}p^i-\sum_{i=0}^{k-j}\binom{n-j}{i}p^i$

那么把可以相像的项写道一起得到：

$\sum_{i=0}^{k-j}p^i\left[\binom{n-j+1}{i}-\binom{n-j}{i}\right]+\binom{n-j+1}{k-j+1}p^{k-j+1}$

因为组合数的意义有：

$\sum_{i=0}^{k-j}p^i\left[{n-j\choose i}+{n-j\choose i-1}-\binom{n-j}{i}\right]+\binom{n-j+1}{k-j+1}p^{k-j+1}$

整理得到：

$\sum_{i=0}^{k-j}\binom{n-j}{i-1}p^i+\binom{n-j+1}{k-j+1}p^{k-j+1}$

同样的处理掉组合数里的 $i-1$ 得到：

$p\sum_{i=0}^{k-j-1}\binom{n-j}{i}p^i+\binom{n-j+1}{k-j+1}p^{k-j+1}$

考虑把 $f(j)$ 带入上式：

$p\left[f(j)-\binom{n-j}{k-j}p^{k-j}\right]+\binom{n-j+1}{k-j+1}p^{k-j+1}$

把式子展开然后提取公因式得到：

$pf(j)+\left[\binom{n-j+1}{k-j+1}-\binom{n-j}{k-j}\right]p^{k-j+1}$

根据组合数的性质，类似与上面的化简得到：

$pf(j)+\binom{n-j}{k-j+1}p^{k-j+1}$

也就是：

$f(j-1)-f(j)=pf(j)+\binom{n-j}{k-j+1}p^{k-j+1}$

消元得到：

$f(j-1)=(p+1)f(j)+\dfrac{n^{\underline{k+1}}}{n^{\underline{j}}(k-j+1)!}p^{k-j+1}$

带入容易得到 $f(\min\{n,k\})=1$，所以原式就是：

$\sum_{j=0}^k\dfrac{j^k(-p)^jn^{\underline{j}}}{j!}f(j)$

注意 $p$ 的符号变了，记得递推的时候处理。

所有操作的时间复杂度均为 $O(k)$，这个问题就解决了。

gym 102331 J Jiry Matchings

做这个题之前需要了解一些前置知识。

定义一个排列是凸序列，当且仅当满足这个序列的差分数组单调不升；反之如果这个序列的差分数组单调不降，那么这个序列就是凹序列。

$\max/\min,+$ 卷积优化 DP，对于这样的一个转移方程：

$f_{i}=\max\limits_{j+k=i} g_j+h_k$

显然这个玩意可以 $O(n^2)$ 的转移，但是如果 $g$ 和 $h$ 都是凸序列，那么就会有更优的做法。

那么把 $f_0$ 初始化为 $g_0+h_0$，然后把两个序列看成：

$\begin{array}{}g_1-g_0,g_2-g_1,g_3-g_2,\cdots,g_{n}-g_{n-1}\\h_1-h_0,h_2-h_1,h_3-h_2,\cdots,h_{n}-h_{n-1}\end{array}$

那么求解 $f_k$ 就相当于在两个序列的开头分别选择一些元素，要求总共选择 $k$ 个元素，然后加上 $f_0$。

因为这两个序列都是上凸的，所以其差分数组是单调不升的，于是贪心的维护两个指针选择最开头的元素中大的那一个就行了，这样也就是可以在 $O(n)$ 的时间复杂度里求解了。

不知道有没有人听说过闵可夫斯基和。

设在以 $x$ 为根的子树中，选择 $i$ 条边且 $x$ 可以被选择得到的匹配的最大值为 $f_{x,i}$。

注意，这里必须是可以选择，否则因为一些神奇的原因 $f$ 不会是一个凸序列。

类似的，设不被选择的最大值为 $g_{x,i}$。

观察发现 $f_x$ 和 $g_x$ 都是凸序列，zjk 都不会证你觉得我会吗。

感性理解一下，树是一个二分图，带权的二分图匹配可以转化成费用流，因为是费用流所以可以通过 zjk 都不会的证明得到是一个凸序列。

显然这样有一个暴力的 DP 转移，在合并的时候是一个类似于背包的转移，仔细观察发现是一个 $\max,+$ 的卷积，刚好可以用凸排列优化，所以我们就可以线性的合并。

但是即使可以线性的合并，但是这样的状态数还是 $O(n^2)$ 的无法通过，使用分治和树剖优化。

考虑减少状态数，即只求解每一个重链的头的 $f$ 和 $g$ 的值。

对于一个重链上的点，先只考虑非重儿子的合并。

考虑递归求解，这样所有的非中儿子的 $f,g$ 都已经求解出来了。

用 FFT 的思想进行分治，每一次把轻儿子分成两半然后合并。

考虑分析时间复杂度，建出递归树，因为每一次区间长度都会减半所以最多只有 $\log n$ 层。

通过 $\max,+$ 卷积合并两个长度为 $o,p$ 的 $f,g$ 的时间复杂度显然为 $O(o+p)$。

假设所有的轻儿子的 $f,g$ 的项数之和为 $m$，那么一层所需的时间复杂度就是 $O(m)$。

因为总共有 $\log n$ 层，所以显然处理轻儿子所需的时间复杂度为 $O(m\log n)$。

通过这个方式合并出轻儿子之后考虑对这个重链上的点进行分治，设 $h_{l,r,0/1,0,1}$ 表示合并了 $[l,r]$ 这个区间，左右端点是否可以选择得到的 $f$ 和 $g$ 的值。

那么同样的如果长度为 $n$，那么用类似上面的分治方法就可以做到 $\log n$ 次合并操作。

因为 $h_{l,r}$ 的项数并不会多于所有的轻儿子的子树的和，所以我们也可以做到 $O(m\log n)$ 的合并。

考虑上面的操作，所有的时间复杂度相加得到最终的时间复杂度为 $O(\sum m\log n)$。

对于树剖，有性质任意一个点到根节点的所经过的重链数量都不会超过 $\log n$。

如果一个节点是重链的开头，那么必然存在一个兄弟节点的大小大于自己，所以这个节点子树的大小至少都会是其父节点的一半。

因为大小每一次都会减半，所以重链最深只会有 $\log n$ 个，自然一个节点向上遍历遇到的重链也不会超过 $\log n$ 条。

对于每一个节点，对于 $\sum m$ 的贡献只会在脱离自己的重链时被计算一次，所以 $(\sum m)=n\log n$，最终的复杂度也就是 $O(n\log^2 n)$。