思维题选做

首先有一个朴素的 dp， 是 $\mathcal{O}(n^4)$ 的

注意到它要多次枚举儿子所以多了一个 $\mathcal{O}(n)$，但也导致了重复运算

因此考虑换一个方向，由儿子确定父亲，或者说在儿子处就确定好一些东西

具体来说，我们在父亲处的做法是枚举所有可能的根，然后对应这个根枚举所有可能的儿子区间及其对应的根，这样我们要枚举两次根

但是我们注意到在儿子处枚举时，其父亲结点可能的根不是 $l-1$ 就是 $r+1$，因此可以少枚举一次根

这样子的话就可以省一维

还是比较有启发性的

我们考虑朴素的做法，列出其方程：

注意到这是一个与卷积的形式，因此考虑 FWT。

然而暴力的 FWT 复杂度还是不对，不过注意到每一次 FWT 前只有 $a_i$ 这一位是 $1$。

手模一下 FWT 的过程不难发现， FWT 之后每一位仍然最多是 $1$，因此卷起来之后所有为 $1$ 的位置的 $f$ 都会翻倍。

因此我们考虑把所有 FWT 的过程加起来一起算，那么每一位的最终结果就是 $2^x$。

然后还要 FWT 回去，最终答案就是 $f_0$。

另外注意到全 $0$ 的时候会多算一个空集，去掉就好。

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

一眼 DP，然后发现直接处理 $a$ 序列不是很好搞。

注意到最终只剩下一条路径，因此可以直接对最后的跳跃序列跑 DP。

考虑设 $f_{i,j}$ 表示 $i, j$ 为跳跃序列最后两个元素要删除的 $j$ 之前的点的个数。

考虑转移：（默认 $i$ 能到达 $j$，不能到达直接设为 $\infty$）

这个式子显然 $\mathcal{O}(n^3)$，因此考虑优化。

后面一项很好处理，我们考虑前一项的处理方式。

然后我们考虑 $k$ 合法的条件，首先发现 $k$ 是一个 $[1,i)$ 区间内的前缀。

我们考虑枚举 $k$，然后拿它对所有 $j > (a_k+k)$ 产生贡献，注意到这是一个后缀。

因此可以考虑在对应的 $(a_k+k)+1$ 上打上 tag 然后用前缀 $\min$ 的方式贡献所有合法的位置。

最后递推地把第二项加上就行，复杂度 $\mathcal{O}(n^2)$。

显然直径产生于两个叶子之间。

我们要做的是尽可能的把边权均摊掉，因此我们不妨随便取一个点作为根然后看看贪心策略。

注意到如果一条边不连接叶子，那么它会使得多个叶子深度增加，这显然没有取在与叶子相连的边上优。

因此答案就是 $s$ 平均分给每一个叶子的返祖边，然后 $\times 2$ 即可。

首先有个结论是答案中相同的字符相邻严格不劣。

那么做已经很好做了，直接枚举全排列求个逆序对取个 $\max$ 就行。

假设原序列中只有两种字符，显然这个结论可以扩展到多种字符时。

考虑此时交换次数是什么，我们不妨选择其中一个字符为关键字符 $key$，那么答案就是两个序列的这玩意儿：

的差值的绝对值。

显然这东西的上下界是就是所有相同字符相邻的那两种情况，显然存在其中一种与原序列差值最大。

首先注意到 $a_i \ge a_{i+1}$ 的位置没有意义，因此可以考虑把序列缩成一个上升子序列。

考虑每一项就是上一项翻几倍然后多出来一小节，翻倍可以考虑从后往前逆推，最后求出最后一项到底是第一项翻了几倍。

然后考虑多出来的一小节，我们考虑直接把它截下来然后插入到序列当中，那么只需要找到它的前驱即可，具体实现的时候可以直接暴力递归。

注意到每一次这一小节都是对上一项取模，因此最多 $\mathcal{O}(\log n)$ 次，总复杂度就是 $\mathcal{O}(\log^2 n)$。

首先我们不难发现， $t$ 串的开头那个字符一定对应的是 $s$ 串的一个前缀。因此我们只需要枚举这个字符对应串的长度就可以唯一确定它对应的串。

然后我们注意到 $t$ 串中 $0/1$ 的出现次数我们都可以知道，我们又知道了某个字符的长度，那么另一个字符对应串的长度我们也能确定。

考虑我们扫一遍 $t$ 串，由于每一个字符对应的字符串长度我们都已知，因此若我们 $\mathcal{O}(|t|)$ 扫一遍 $t$ 串，就可以求出每一个字符在 $s$ 串中对应的 起始位置。

再加上我们确定的长度，每一个字符在 $s$ 中对应的串我们可以通过哈希 $\mathcal{O}(1)$ 求得，因此我们得到了一个 $\mathcal{O}(|t|)$ 判断一组长度是否合法的算法。

但是这样看起来还是 $\mathcal{O}(|s||t|)$ 的，不过注意到在 $t$ 串中，出现次数更多的那一个字符的出现次数一定 $\ge \frac{|t|}{2}$。

因此我们枚举这一个字符，显然另一个字符的长度还是可以 $\mathcal{O}(1)$ 求，而且我们枚举的上界只需要达到 $\mathcal{O}(\frac{|s|}{|t|})$。

因此最终复杂度分析出来是 $\mathcal{O}(\frac{|s|}{|t|})\times\mathcal{O}(|t|)=\mathcal{O}(|s|)$ 的。

DPair $\leftarrow$ 全机房做语言最晚的人。

其实看完题解冷静了一下感觉这题还是比较可做的，看来对树上连通块问题还是不够熟悉。

首先我们得找到一种方便的计算答案的方式，注意到每一个结点可达的所有点形成一个连通块，考虑能否对于每一个结点快速处理出这个连通块大小，若能的话就可以快速处理出答案。

我们考虑这个连通块显然是有特殊性质的，注意到它的所有端点的集合就是所有过当前点的路径的端点形成的集合。

然后考虑怎么处理这个东西，注意到我们首先得处理这样一个问题：“给你一个点集，求出覆盖这个点集的最小连通块。”

这种问题一般就是用虚树来处理了，考虑建出所有点的虚树，注意到答案就是虚树上所有边的长度之和 $+1$。

注意到我们建虚树时一般都要钦定 $1$ 号结点加入，因此点集内所有点的 LCA 是被多算了的，额外处理一下即可。

然后考虑这个做法怎么扩展。

不难发现我们已经把比较重要的点数缩小到了 $\mathcal{O}(q)$ 级别，我们只需要实时能够维护出这些点会影响到那些区间即可。

那么我们现在类似于在做一个树上动态集合的问题，不难想到线段树合并+树上差分。

现在我们只需要快速维护出每一个线段树状态下连通块的答案即可，说白了就是线段树维护虚树。

我们考虑我们建虚树的时候，是按 dfn 序排序之后进行一些操作，因此这里我们也考虑 dfn 序建线段树。

我们对于每一个线段树上的结点维护出其区间内最左和最右两个结点的标号，顺便维护出区间答案，这样我们最后求出线段树根节点的答案减去最左最右 LCA 的深度就是答案。

考虑合并两个区间时，最左最右的结点编号都好维护，考虑答案的维护。

不难发现我们建虚树时，插入一个新点带来的边权增加就是它与最后一个结点的 LCA 距离。

那么假设我们固定左区间合并右区间，虽然我们不能依次添加右区间的所有点，但是注意到我们添加完右区间最左边的点后，剩下的和左区间就没有关系了。

因此我们只需要求左区间最右和右区间最左节点 LCA 的深度，答案减去它就行。

我们只要 $\mathcal{O}(1)$ LCA 套上去就是 $\mathcal{O}(n\log n)$ 的了。

说句闲话，sooke 爷的题解怎么一股子天津味儿

首先显然到根距离 $> k$ 的点没有意义，因为到达深度 $=k$ 就结束了。

然后子树内最大深度 $< k$ 的点也没有意义，因为到了就死了。

所以有意义的就是所有到根距离为 $k$ 的点到根的链的并，因此这棵树现在所有叶子深度都是 $k$。

不难发现先手第 $i$ 次堵点一定堵深度为 $i$ 的最优，注意到此时每一次堵点至少删掉 $k-i+1$ 个点。

因此删完 $k$ 次之后点数是 $n-k^2$ 级别的，可见这棵树要满足 $n > k^2$ 才有可能后手赢，因此 $k$ 是 $\mathcal{O}(\sqrt{n})$ 级别的，更大的都是先手必胜。

注意到这样子的话 $k$ 只有 $20$ 的样子，我们又是每一层删一个。

因此考虑状压 dp。

首先这题是子树问题，因此我们考虑拉出序列的 dfs 序。

设 $f_{i,S}$ 表示选取深度集合为 $S$ 的点，能否覆盖 $i$ 以后的所有叶子。

考虑转移，首先若一个点不是叶子，那么若 $i+1$ 可以覆盖那么它本身显然也可以覆盖，而且当前点不需要选。

然后我们考虑枚举当前点选的情况，不难发现我们只需要 $i+sz_x$ 能被覆盖即可。

因此把该处理的处理出来直接转移即可，复杂度 $\mathcal{O}(n2^{\min(k, \sqrt{n})})$。

首先判等其实很好判，注意到我们要分类处理，只有字符集合完全相同的串可以分到一类。

因此每一个串排个序然后开一棵 Trie 上面每一个点是一个 vector 就行，然后每一个串都会产生与其不在一个集合内的点 $\times 1337$ 的贡献，多算的部分最后处理一下即可。

考虑对于字符集合相同的怎么处理。

首先答案显然是 $\le 2$ 的，因为你两个串都排一遍序即可。

现在只需要考虑操作次数是 $1$ 的有多少对，那么减掉就行。

注意到此时两个串的一段前缀和一段后缀相同，剩下的一段在某串内有序。

考虑到确定对应的前后缀比较困难，因此考虑处理有序段。

不难发现我们上述的 “在某串内有序”，若这个有序段不是极长的，则它扩展为极长之后对应的前后缀仍然匹配，因此考虑处理出每一个串的所有极长有序串。

现在要处理的就是对于一组前缀后缀，有多少串既以这段前缀为前缀又以这段后缀为后缀。

考虑建正反串的 Trie 树，那么对于 Trie 树上的每一个点，对应了其子树内所有叶子的一个前缀（后缀）。

注意到实际上就是两个子树查询取并，不过仔细思考一下发现其实就是一个二维数点。

考虑为什么这样不会算重，考虑串 $a$ 的某一段区间已经在 $b$ 中匹配上，那么串 $b$ 中的这一段区间一定和 $a$ 中这一段区间不同，因此下一次匹配时这两个串一定不会匹配上。

复杂度 $\mathcal{O}(\sum |s| \log \sum|s|)$

DPair $\leftarrow$ 全机房做保卫王国最晚的人。

首先由于 最小权覆盖集=点权和-最大权独立集，因此把钦定状态设成正负无限，就是一个动态 DP 的板子。

我不会动态 DP 所以考虑更有针对性的做法。

不会，咕了