果然字符串的终点和字符串没什么关系吗。

不难发现我们每次只会在一个长竹竿后面拼接一个基础的短竹竿来增加长度。假设每次拼接竹竿的重叠部分为 $p$，显然 $p$ 是字符串的一个 border。

我们可以把这个字符串的所有 border 求出来，得到一个大小为 $m$ 的集合 $\{b_i\}$。最后要求的就是满足 $v\in [0,w-n]$，且方程 $\sum_{i=1}^m b_ix_i=v$ 存在解的 $v$ 的数量。

好的，后面是一个经典的同余最短路问题，于是我们得到了一个 $\min{b_i}\times n$ 的解法，但是这个做法是 $O(n^2)$ 的。

考虑优化这个做法，经典结论是一个字符串的 border 可以划分成 $\log n$ 段等差数列 $d_i+c_il_i$（结论证明较为复杂）。考虑对于每一个 $i$，求出在 $\bmod d_i$ 意义下，加入前 $i$ 个等差数列对应的边后的最短路。

依次加入每个等差数列，计算对最短路的影响。先考虑将原来 $\bmod d_{i-1}$

........................................................................

该题解待审

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19373303

此题目前无 spj，遂 30 pts.

大意

$m$ 对关系 $(u, v)$，第 $i$ 对表示 $i$ 这个点可以选择 $u$ 或 $v$。求最大的选择题数的方案数和方案。

（如果一道题做不出来就无法进行下一道题目）

思路

考虑二分图最大匹配。

实则并不算最大匹配，我们通过读题可以发现其实就是二分图匹配的过程，每次找一条增广路，如果找不到了，就说明当前无法继续进行这个游戏了。

也就是在匹配的过程中记录答案，如果找不到增广路径，那就直接 break 即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359545

考虑树上背包。

定义状态 $f_{u, j}$ 表示 $u$ 节点，切掉 $j$ 个所需的最小花费。

那么我们的初始状态就是 $f_{u, 0} = 0$, $f_{u, sz_u} = 1$。

然后我们考虑如何进行转移：

$f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{v, k})$

然后考虑我们的答案如何进行计算，显然是 $f_{u, sz_u - p} + f_{u, sz_u}$，这个地方的 $f_{u, sz_u}$ 的值显然是 $1$，但是只有根节点是 $0$。

这个地方实际上就是为了让你的选出来的这 $p$ 个点与你原来的 $u$ 子树脱离，显然需要你删一条父边。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359481

首先，这个题目的建图太抽象了，需要好好理解一下。

然后我们考虑树上背包。

我们定义 $f_{u, j}$ 表示，在 $u$ 这颗子树内选择 $j$ 个叶子节点的最大收益（叶子点权和 $-$ 需要的边权和）。

那么我们显然有转移：

$ f_{u, j} = \max(f_{u, j}, f_{u, j - k} + f_{v, k} + w(u, v)) $

显然如果你选择了 $v$ 这个子树所产生的收益，那么你就必须承担 $u - v$ 这条边的代价。

然后随便作一些上下界优化即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19346416

首先考虑 $\mathcal{O}(n ^ 2)$ 的解法。

枚举每条边，然后分别统计左右子树的重心，然后想加即可。

然后考虑优化，显然我们的复杂度浪费在了找重心的地方。

“一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。”——OIwiki

有关树的重心的内容见OI-wiki/树的重心

重心必在节点的「重儿子链」上（重儿子指子树大小最大的子节点），因此可通过倍增沿重儿子链快速定位重心候选。

删除边 $(u, v)$ 后，$u$ 所在的大子树（大小 $n - sz_v$）需要「换根」更新重儿子（原重儿子可能是 $v$，需替换为次重儿子或父方向），而 $v$ 所在的小子树（大小 $sz_v$)）是原树的子树，无需换根。

节点最大子树（含父方向）≤ 总大小 / $2$ 则为重心。

递归算每个节点的子树大小，记录重 / 次重儿子（子树最大 / 次大的子节点），构建倍增数组（沿重儿子链跳，$\mathcal{O}(\log n)$ 找重心）。

然后累加答案即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19343265

首先考虑用线段树做。

发现数据范围很大，但是实则不需要考虑啊，因为我们的海报的数量一定，可以考虑离散化去重，然后用线段树做。

每次更改一段区间的话，采用标记延迟下传的方式，如果在目标区间就先打上懒标记，如果以后访问到了再下传，这样就不必要每次放到叶子上了。

最终查询就直接访问所有叶子就好，用个 set 去重海报。