场上想出了正解太复杂了以为假了没写，结果赛后发现和正解一模一样，空悲切。

首先这一看就能 dp，考虑设 $f_i$ 表示以 $i$ 为根的子树分为若干链的最小代价，每次枚举一条以 $i$ 为端点的链，枚举另外一端 $j$。

考虑贡献，首先有这条链的贡献，其次有 $j$ 的所有儿子的子树划分为链的贡献，然后又 $i\to j$ 路径上，因为把 $i\to j$ 割掉后分出的各个子树的贡献。

设 $h_u=\sum_{v\in son(u)}f_v,g_u=\sum_{v\in bro(u)}f_v$，另外设 $s_u$ 表示根到 $u$ 的所有边权之和，$sg_u$ 表示根到 $u$ 的 $g_i$ 之和，不难写出一个转移：

$$f_u=\min_{v\in Subtree(u)}\{h_v+(s_v-s_u)^2+C+(sg_v - sg_u)\}$$

如果暴力转移，$h,g,sg$ 都可以 $O(n)$ 处理，主要是 $f$ 的转移是 $O(n^2)$ 的。

注意到这是一个经典的斜率优化形式，考虑斜率优化，因为在树上进行，考虑李超树，唯一的问题是直线的截距 $sg_u$ 可能会需要子树加。

实际上，在合并李超树的时候，顺路维护一个全局加的标记即可，这个标记可以在合并的时候打在根上。

时间复杂度为 $O(n\log n)$。

完美匹配(match)

给定 $n$ 个 $a_i$ 和 $m$ 个 $b_i$，要求满足 $a_i + b_j \ge S$ 且 $|a_i - b_j| \le D$ 的可以配对一次，每一个 $a_i$ 或 $b_i$ 只能配对一次，问最大配对方案。

对于特殊性质 $\text{A}$：满足 $D = 10 ^ 9$。

测试点 1 ~ 2 (20pts)

由于 $n, m \le 10$，所以，我们可以暴力的去 DFS，每次为当前的试卷找一个配对的人，时间复杂度 $\mathcal{O}(m ^n \times n)$。

实现略。

测试点 3 ~ 4 （20pts）

由于 $n, m \le 1000$，我们就可以考虑 $nm$ 的做法。

匹配的问题，不可避免的可以想到去跑二分图匹配，只要我们能把边建出来。

对于建边的过程，我们可以选择 $\mathcal{O}(nm)$ 的去判断是否可以配对，连边。

连完边之后我们就可以直接进行二分图最大匹配。而二分图最大匹配的复杂度理论是 $\mathcal{O}(nm)$，可以通过。

测试点 5 ~ 6 （20pts）

因为 $D \le 10 ^ 9$，因此对于任意的 $a_i, b_j \in [1, 10 ^ 9]$，一定有 $|a_i - b_j| \le D$，所以我们现在只有第一个条件需要看。

第一个条件很简单，就是 $a_i + b_j \ge S$。

我们要选择尽可能多的匹配。

我们可以把这个式子转化一下，那么对于 $b_i$ 来说，就是 $b_i \ge S- a_i$，我们令 $c_i = S - a_i$，那么对于每一个 $b_i$ 只有让 $c_j \le b_i$ 的时候，就可以让这个 $a_j$ 和 $b_i$ 进行配合。

那就很简单了，我们只需要把 $c_i$ 和 $b_i$ 进行升序排序，我们对于每一个 $b_i$ 可以选择最大的 $\le b_i$ 的 $c_i$，这个过程可以利用双指针，或者放一个堆。

时间复杂度 $\mathcal{O}(n \log n)$

测试点 7 ~ 10 (40pts)

实际上对于特殊性质 $A$ 来说，已经给了我们一些提示，那就可以把这个不等式进行转化：

首先是我们还是先以 $b_i$ 为主，那么就可以转化为，$b_j \ge S - a_i$，第二个不等式我们可以把绝对值拆开，左边是 $b_j \ge a_i - D$，右边就是 $b_j \le a_i + D$。

那么对于每一个 $b_j$ 来说，我们能选到的就是区间 $[\max(S - a_i , a_i - D), a_i + D]$。

因此现在的问题就变为了，现在有若干个区间，和若干个点，每一个点只能匹配一个区间，问最大的匹配数量。这是一个很经典的贪心模型，我们直接对于每一个区间按左端点排序，对于每一个 $b_j$ 也按是升序排序，我们遍历每一个 $b_i$，对于每一个 $b_i$ 来说，我们能选择的是覆盖这个点的 $r$ 最小的区间，那么这个过程我们可以直接用一个小根堆维护。

时间复杂度 $\mathcal{O}(n \log n)$

点击查看题解文档

点击查看题解文档

字符串练手题，不算太难。用字符串 $t$ 代指询问的串 $w$。

首先仔细琢磨一下，发现 $kq\le 10^5$，这启发对 $k$ 进行阈值分治，设阈值为 $B$。

对于 $k\ge B$，发现 $q$ 比较小，考虑对于每个询问，直接枚举所有 $i\in[a,b]$ 的 $[l_i,r_i]$ 来计算答案，对 $s$ 建立 SAM，并让 $t$ 的每个前缀 $t_i$ 跑出与 $s$ 子串匹配的最长后缀长度 $w_i$ 以及其对应的状态 $p_i$，若 $t_{l\sim r}$ 在 $s$ 中存在，则满足 $w_r\ge r-l+1$，对于其出现次数，只需要得到 $t_{l\sim r}$ 在 SAM 上对应的位置即可，预处理后缀树的倍增数组，跳到最后一个满足 $len_f\ge r-l+1$ 的 $p_r$ 的祖先 $f$，查询 $f$ 状态对应的 endpos 集合大小即可，预处理即可。

对于 $k<B$，注意到可以直接枚举 $t$ 的所有子串 $t_{l,r}$，并计算这个子串在 $s$ 的出现次数，同时计算区间 $[l,r]$ 在 $[a,b]$ 这个范围内出现多少次。对于前者，固定 $l$ 移动 $r$ 做匹配，匹配失败后面就直接退出，预处理后缀树的 endpos 集合大小即可计算次数，对于后者，拿 vector 存下每个区间在区间序列中出现的位置，然后二分查找计算出现次数即可。

理论复杂度可以做到 $O(n\sqrt{n\log n})$，两个部分都是，不知道能不能做到更优，实测取 $B=500$ 能过

本来还有 $30$ 分给多项式的，但是阻碍了伟大的 hxf 的 AK 之路，考虑到 CCF 不会出多项式，所以去掉了这一部分。

正难则反，考虑去算有那几步是不会产生贡献的，若第 $i$ 步不会产生贡献，则说明之前已经走到过这里一次了。

枚举第 $i$ 步所在的格子在 $t$ 步之前已经来到过这里了，设 $f_i$ 表示从一个位置出发，走 $i$ 步又回来，期间不经过这个位置的方案数。限制中间不经过是为了防止算重，求出 $f$ 后，答案为 $\sum_{i=1}^n\sum_{t=1}^if_t4^{n-t}$，不难发现这个式子和 $i$ 无关，继续化简为 $\sum_{t=1}^nf_t4^{n-t}(n-t+1)$。

问题是如何求出 $f$，考虑单步容斥，先求出 $g_i$ 表示从一个位置出发，走 $i$ 步又回来的方案数，则有 $f_i=g_i-\sum_{j=1}^{i}f_jg_{i-j}$。

对于 $g_i$，可以枚举竖直方向走了多少步，水平方向走了多少步，组合起来，通过组合恒等式可以证明当 $i$ 为偶数时，$g_i=(C_{i}^{i/2})^2$。另外一个方法是旋转坐标系 $45$ 度，无论上下左右都相当于在竖直和水平上都选择一个方向走一个单位长度，也能直接得到这个结论。

直接计算即可，瓶颈在于求 $f$，实际上可以用多项式优化，但是不是很文明所以去掉了。朴素实现是 $O(n^2)$，多项式是 $O(n\log n)$，听说存在 $O(n)$ 的做法。