如果没有不能相邻两次走同一条边的限制，可以直接矩阵快速幂。对于这样的限制，整体地考虑所有路径，进行容斥亦不现实。

所以回归矩阵乘法做图上路径计数的本质——动态规划。

设 $f_t(i,j)$ 为 $i\to j$ 长为 $t$，且不走回头路的路径数量，那么对于 $t\ge3$ 有递推式

$$\displaylines{f_t(i,j)=\sum_k f_{t-1}(i,k)f(k,j)-(d_j-1)f_{t-2}(i,j) }$$

其中 $d_i$ 等于 $i$ 的度。那么令矩阵 $G_t$ 第 $i$ 行第 $j$ 列为 $f_t(i,j)$，$G_1=G$ 即为原图邻接矩阵，上式等同于

$$\displaylines{G_t=G_{t-1}G-(D-I)G_{t-2} }$$

其中 $D=\mathrm{diag}(d_1,d_2,\cdots,d_n)$。不难发现上式可以矩阵加速：

$$\displaylines{\begin{bmatrix}O&I\\I-D&G\end{bmatrix} \begin{bmatrix}G_{t-2}\\G_{t-1}\end{bmatrix} =\begin{bmatrix}G_{t-1}\\G\end{bmatrix} }$$

矩阵套矩阵，喵喵题。

询问有多少种选取的方案，使得取出的集合的并包含给定集合。

一眼 NP，于是考虑暴力容斥。

将选出集合的并包含给定集合 $\{a_1,a_2,\cdots,a_n\}$ 看作选出的集合并包含 $a_1$ 且包含 $a_2$ 且包含 $a_3$……。经过一步容斥后转化为选出的集合并不包含 $b_1$ 且不包含 $b_2$ 且不包含 $b_3$……（其中 $\{b_1,b_2,\cdots,b_n\}\subseteq\{a_1,a_2,\cdots,a_n\}$），也就是对于询问集合的每个子集，求可选集合中与它不交的有多少个。

暴力显然不可取，考虑到质因数分解带自然根号：每个质因数至多有一个不小于 $\sqrt n$ 的质因子。所以我们只用状压前 13 个质数，单独讨论最大的质数即可。

我们令任一重心作为根，分类统计。

一棵树的重心要么是根，要么在重儿子内，换言之，在重链上。

那么每个子树的重心可以均摊 $O(1)$ 地从其重儿子子树重心开始向上寻找。

对于一整棵树去掉一个子树后剩余的连通块，分类讨论：

如果删掉的部分不在重儿子内，此时删掉的部分大小相同，剩下部分重心一定相同。所以我们只需要从小到大枚举删掉部分的大小，同时向上移动整棵树的重心，时间复杂度 $O(n)$。另统计出轻儿子子树内，某个大小的子树各有多少棵。

如果删掉部分在重儿子内，而删掉后重儿子仍然是重儿子，剩余部分的重心仍然在重链上，并且一定不比原重心低，只能是根。

否则次重儿子会成为重儿子。此时类似地统计出删除重儿子内某个大小的子树后重心是谁，以及重儿子内某个大小的子树各有多少颗。

对于方案难以通过贪心或 DP 直接构造的题目，可以尝试二分答案后贪心或 DP。

以及这道题要求所有树长成时间的最大值最小，提示我们二分答案。

对于每个节点，给定它长成的最后期限后，可以计算出种下它的最后期限。

至于父亲种下时间 $t_u$ 必须早于儿子种下时间 $t_v$ 的限制，我们令

$$\displaylines{t'_u=\min\{t_u,\min_v t_v-1\} }$$

以 $t'_u$ 为修正后的种植最后期限，忽略祖先关系之间的限制，如果能够构造出任意一组合法方案，那么不断交换所有不满足限制的父亲和儿子，一定在有限步内结束，构造出一组满足限制的方案。

判断是否存在一组忽略祖先关系限制后的方案，只需按照 $t_u'$ 从小到大排序，贪心选取即可。

给定一个串，它是可消除的，当且仅当存在两个相邻的位置字符相等，并且删去它们后剩下的字符串是可消除的。

如果这个串中出现了多个相邻的位置字符相等呢？我们如何找到删哪个字符能够构成一个可消除字符串呢？

经过简单考虑后不难发现，一个串如果是可消除的，那么第一步删除任意一组相邻相等字符都可以得到一个可消除串。

如果一个串可消除，找出它的任意一组消除方案，其中记与位置 $x$ 一同被删除的是位置 $\hat x$。对于任意一组相邻相等字符 $u,v$（$u<v$），如果 $u=\hat v$，那么在原方案中将“删除 $u,v$”这一步放到最开始做，其余步骤不变，仍然合法；否则不难发现原方案中 $\hat u,\hat v$ 之间（不含端点）的子串一定是内部相互配对，那么我们先消除 $u,v$，在删除 $\hat u,\hat v$ 之间的子串后删除 $\hat u,\hat v$，仍然合法。

所以我们从前往后考察每个位置，并维护一个栈表示已经做完的前缀中未被匹配的字符。如果当前位置和栈顶相等，立即匹配，弹出栈顶；否则压入栈。显然该串可消除当且仅当结束时栈为空。

---

原问题是询问这样的可消除子串有多少个。

可以把每个点都作为起点扫一遍，每当栈为空就统计一次，时间复杂度 $O(n^2)$。

显然我们只能对整个序列扫一次。考虑到一个子串可被消除当且仅当，加入它的第一个位置前，和加入它的最后一个位置后，两个时刻栈相等。对栈进行哈希，每个位置结束后进行统计即可。

区间在线逆序对板子。

块内分别记录下排序后的结果，并对每个块分别预处理，块内所有前缀和后缀内逆序对个数，以及对于每个 $k\in[1,n]$，块中有多少大于等于 $k$ 的数。

这样就可以很方便求出 $f_{i,j}$ 表示有多少这样的逆序对，使得第一个数在前缀 $[1,j)$ 中，第二个数在块 $i$ 中；$g_{i,j}$ 表示有多少这样的逆序对，使得第一个数在块 $i$ 中，第二个数在后缀 $[j,n)$ 中。对于每个块我们只需要考虑与其不交的前/后缀即可。

然后我们将所有逆序对分为四种：

• 两个数在同一块内，$O(\frac nB)$ 对所有整块，以及两个散块的前后缀和求和得到；
• 第二个数在整块内，讨论第二个数在哪个整块，那么第一个数就被限制在一个区间内，将区间表示为两个前缀相减，通过 $f$ 求出；
• 第二个数在右端散块内，第一个数在整块内，讨论第一个数在哪个整块，第二个数就被限制在右端散块这个区间内，表示为两个后缀相减，通过 $g$ 求出；
• 第二个数在右端散块内，第一个数在左端散块内，对两端块排序过后的数组双指针统计。

如果询问的区间完全被包含在一个块内，考虑容斥，设块左端点为 $t$，用 $[t,r)$ 内的逆序对数减去 $[t,l)$ 内的逆序对数和左端点在 $[t,l)$ 且右端点在 $[l,r)$ 内的逆序对数集合即可，其中前两部分已经预处理过，第三部分可以对该块排序后的数组进行简单的统计。

单点修改，树上查询邻域点权和。

如果不带修的话是经典题目树上邻域数点的弱化版，因为查询时合并簇的次数限制从一次放宽到了 $O(\log n)$ 次。

具体做法是建出全局平衡二叉树，对于每个簇的某个界点 $u$，设 $d$ 为簇内到 $u$ 距离最远的点的距离，对于每个 $k\in[1,d]$ 维护簇内于 $u$ 相距为 $k$ 的点的点权和。全局平衡二叉树处理簇内点相关信息时一般不包含界点，否则不方便统计答案，这里同理。

于是树上单点修改 $u$ 的点权时，从包含 $u$ 的最小簇（$u$ 不能是该簇界点）开始向父亲跳。对途径的每个簇维护的距离两个界点相应距离的点的权值和进行单点修改。

查询以 $u$ 为中心的邻域时，将邻域分解为几个整簇和几个簇内邻域进行合并。具体做法是从以 $u$ 为界点的任一簇开始往父亲跳，对途径的每个点，考察邻域是否覆盖到了它的兄弟，它兄弟的界点是否在父亲的簇内。一通合并后记得考察根簇的界点是否在邻域内。

簇内查询邻域需要对所维护的到两个节点距离为定值的点的权值和求前缀和，还需要单点修改，所以使用树状数组查询。

从前往后依次考虑每个段，不难发现，某个段内要么不表演，要么在不与之前的表演冲突的前提下，尽可能多地表演，即不需要迁就后面的段而让当前的段少表演，否则将后面段的表演移到前面段来，一定不劣。

既然如此，我们只需要 DP 求前 $i$ 段中最多唱多少首歌，设为 $f_i$；在唱最多歌的基础上，最早什么时候结束，设为 $g_i$。

暴力转移是 $O(n^2)$ 的。

考虑满足 $g_j\le l_i-t$ 的转移 $j\to i$，$i$ 段的决策一定是从 $l_i$ 开始唱歌，所以在只从最后一个这样的 $j$ 更新，一定不劣。

而对于 $g_j>l_i-t$ 的所有转移 $j\to i$，每个 $j$ 在整个过程中最多进行一次这样的转移，所以可以暴力做。

不难发现一个性质，如果某个方案中老鼠 $i,j$ 分别躲进了洞 $u,v$ 中，$x_i<x_j$ 而 $p_u>p_v$，显然调整为让 $i$ 躲进 $v$，$j$ 躲进 $u$，该方案一定不会变劣。因此，将老鼠按照起点所在的位置划分为几个连续段，这些连续段从左往右依次匹配从左往右的洞，一定不劣。

考虑朴素 DP，设 $f_{i,j}$ 表示前 $i$ 个洞匹配前 $j$ 个老鼠，老鼠需要走的总长度最小值。有

$$\displaylines{\begin{aligned} f_{i,j}&=\min_{k=j-c_i}^j\left\{f_{i-1,k}+\sum_{k<t\le j}|x_t-p_i|\right\}\\ &=\min_{k=j-c_i}^j\{f_{i-1,k}+s_{i,j}-s_{i,k}\}\\ &=s_{i,j}+\min_{k=j-c_i}^j\{f_{i-1,k}-s_{i,k}\} \end{aligned} }$$

其中 $s_{i,j}$ 表示 $\sum_{t\le j}|x_t-p_i|$，并且 $j$ 增大的过程中，$k$ 的合法取值区间单调右移，使用优先队列优化到 $O(nm)$。

鉴于每次只能选择一个质因数取，我们可以将原游戏分解为多个游戏的组合，对于质数 $p$，若 $a_i=p^{\alpha_i}k_i$（其中$p\not\mid k_i$），那么 $p$ 对应的游戏为：

对于集合 $\{\alpha_1,\alpha_2,\cdots,\alpha_n\}$，每次选择正整数 $k$，将集合中所有不小于 $k$ 的数全部减去 $k$，直到所有数全部变为 $0$。

由于 $n\le10^9$，$\alpha_i$ 不超过 $30$，可以状压。状态数上界不会证。

于是可以通过动态规划求出每个 $p$ 对应的游戏，每个状态的 SG 值。通过 SG 定理可以求得原问题起点的 SG 值。