Exercise G

置换题，找环，次数等于所有环长的 $lca$（环独立基本定理），发现这和数有关，考虑数位压缩，显然用质数作状态即可。

$f(i,j)$ 表示前 $i$ 个素数总和为 $j$ 的所有 $k$ 的总和，可以用幂级数统计一个素数的贡献。

概率充电器

有三种可能：
1. 自己通电
2. 子树内通电
3. 子树外通电

子树外可以换根（基本套路）， $f(u)$ 为自己通电和子树内通电的概率，

容斥减去子树没电，子树有电，但是不通电的概率即可。

换根数组 $g(u)$ 表示子树外通电概率，有 $u$ 的父亲的子树外，$u$ 的父亲的子树除了 $u$ 的子树的部分。

第一个贡献显然，关于第二个，因为我们是连乘积形式，所以直接除掉儿子的贡献就完了。

转移的时候拆成子树没电，子树有电，但是不通电的概率即可。

我们的数组直接容斥维护充不上电的概率即可独立转移。

小星星

没有好的思路，定义状态$f[i][j][S]$表示节点$i$编号为$j$，$i$的子树内的编号集合为$S$的方案数，这个定义需要枚举子集，但是限制需要我们将点分三类，复杂度过高，考虑子集反演。

此时我们没有了映射两两不同的限制，$O(n^32^n)$ 即可。

Turtles

本题要求路径不交，充分条件是一条路径选择 $(1,2)$ 到 $(n−1,m)$ ，而第二条则选择 $(2,1)$ 到 $(n,m−1)$。

又因为一条路径选择 $(1,2)$ 到 $(n,m-1)$，而第二条则选择 $(2,1)$ 到 $(n−1,m)$ 则必然会相交。

简单容斥即可。

CHO-Hamsters

字符串总出现次数为 $i$，其中最后出现的字符串为第 $j$ 个字符串。

方便转移，优化在第 $i$ 个字符串后最少添加多少个字符使得当前字符串中也含有 $j$。

这可以用 $KMP$ 解决，此时变成类$floyd$问题，矩阵快速幂优化即可。

邮局

直接做后效性有点严重，考虑逐步优化，

定义$dp[i][j]$表示前$i$个村庄放$j$个邮局的前$i$个村庄的最小距离总和，$w(i,j)$表示村庄区间$[i,j]$内放一个村庄时该区间的最小距离总和。

考虑预处理，由于中位数相邻变化，讨论发现无后效性，可以先递推 $w(i,j)$，复杂度 $O(PV^2)$。

预处理不是瓶颈，状态已无法再简化，显然找单调性，从 $w$ 出发对左右边界微扰分析变化量即可证明四边形不等式，

从而得到$dp$数组的四边形不等式，并得到决策单调性，

因为$dp$数组以已知推未知，需要酌情倒序枚举，势能分析可证优化至 $O(PV)$

Cow Hopscotch G

转移方程有二维偏序关系，使用 $cdq$ 分治，具体地，不用排序，双指针消掉一维偏序，由于转移是一种点对区间的贡献，用树状数组作桶来维护即可。

Cutlet

区间划分问题，只有两类区间，用状态表示，显然由状态等效替代得到状态数组 $f[i][j]$ 表示前 $i$ 秒，当前煎的是正面，背面 煎了 $j$ 秒的最小翻面次数。

不难发现，对于两个区间之间的 $i$，是可以直接跳过的。（背面煎的时间不变）

因此，令 $f[i][j]$ 表示前 $i$ 个区间，到 $r_i$ 时间，背面煎了 $j$ 分钟的最小翻面次数。

显然翻无限次完全没有作用，事实上，一个区间我们最多只需要翻两次，显然可以分类讨论。

考虑翻一次面，枚举在翻面前煎了 $k$ 秒，由于决策点$r−j−k$单调递减，可以用单调队列维护，由于 $k <= r - l$，队列枚举的对应题解中 $r-(j+k)$ 中 $j+k$ 的值（上一轮背面（这翻面后正面）被煎的秒数），及时排除不合法解。

考虑翻两次面，枚举煎了 $k$ 秒后又翻了回去，由于决策点$j−k$单调递增，可以用单调队列维护，由于 $k <= r - l$，队列枚举的对应题解中 $j-k$ 的值（上一次翻到背面（之后又翻回）前的煎的秒数），及时排除不合法解。

Roads in Yusland

设 $f_i$ 表示覆盖 $i$ 子树内的所有边和 $i$ 与其父亲的边的最小权值，

然而这样做有后效性，对于一种覆盖 $i$ 子树内的所有边和 $i$ 与其父亲的边的方案，可能它并不是最小权值，但是它向上延伸得更长。

因此我们要保留住所有可能最优的方案，同时要计算其中的最小值，这启发我们考虑小根堆。具体来说，对于节点 $i$，$i$ 上的小根堆内存储了覆盖 $i$ 子树内的所有边和 $i$ 与其父亲的边的所有可能最优的方案。

一个点有来自多个儿子的小根堆，显然我们需要将它们合并起来，于是将小根堆改为左偏树或可并堆即可，也可以用线段树加启发式合并维护。

同时，我们还需要支持整棵左偏树加上一个定值，打个标记即可。

对于需要扔掉的方案，由于我们不需要实时删除，因此考虑我们暂时先保留它们，当它们成为根时再弹出即可。

这道题充分体现了决策集合和决策点之间的关系。

Leaf Partition

简单构思就会想到在树上 dfs 处理，对每个节点处理出子树的划分方案数，再向上合并。

记录两种状态：

1. $dp_{x,0}$
   表示 $x$ 未被划进任何连通块内，即不存在两个不同儿子所在子树的任何叶子被划进同一连通块（否则 $x$ 也必须划进这个连通块）的包含子树中所有叶子的划分数。
2. $dp_{x,1}$
   表示 $x$ 被划进一个连通块内的包含子树中所有叶子的划分数。

发现这道题包含了子树和向上蔓延两个方面，考虑把儿子遍历一遍，用一个 $tot$ 变量记录前面遍历过的儿子向上蔓延和不向上蔓延的总方案数（前缀积），再用一个 $tot2$ 变量记录前面遍历过的儿子都不向上蔓延的方案数，很明显，$tot−tot2$ 就是前面有至少一个儿子向上延伸了的方案数，乘上这个儿子向上延伸的方案数就是这个儿子对 $dp_{x,1}$ 的贡献。

我们用容斥记录方案时只在后面更新前面的延伸，并保证后面的都不会延伸（通过在遍历下一个儿子时对 $dp_{x,1}$ 乘上下个儿子不向上延伸的方案数实现。

对于 $dp_{x,0}$ 的更新，由于对于一个 $dp_{y,0}$ 的向上蔓延，可能有不止一种的方案，还需要考虑每种方案子树有几个节点可以向上延伸。

于是还需要再引入一个 $dp_{x,2}$，记录对于 $x$ 没有被包含的方案中，有多少个节点是可以向上蔓延的。

$dp_{x,2}$的转移本身就没有多复杂了。

HOT-Hotels 加强版

统计与它距离相等的点的个数，乘法原理计算贡献，

由于信息与深度有关，且对应的位置只整体往后移动了一位。所以我们保留一部分子树信息直接当做当前节点的信息，也就是用长链剖分重叠子结构，分配内存即可。

Tree and Queries

先将所有的询问以离线的方式存储下来，这样子做可以让我们一边$dfs$，一边解决所有的询问。

类似上题，由于空间不够开全局桶，我们贪心地开重儿子上，跳轻边时就暴力统计。

记录$>=k$的颜色数量即可。

Tree Requests

先将所有的询问以离线的方式存储下来，这样子做可以让我们一边$dfs$，一边解决所有的询问。

之后统计所有深度字母的出现次数（二进制压缩即可）以便我们的 $check$ ，核心是将轻边子树的信息保留到重链之上进行一个答案的统计。

重建计划

点分树

首先分数规划（就是二分判定），将问题转化成找树中有没有负的路径，由于有长度限制，考虑点分树，暴力的从分治重心dfs一遍然后求出每一个路径的距离和深度，

现在考虑如何拼合路径，也就是对于每一个路径求出和它匹配的最优的一个路径，但是我们还有深度的限制，换句话说我们能和这个路径匹配的路径的深度必须在一个区间里，无法通过对深度建权值线段树解决。

如果把割掉父节点之后每一个子联通块中的路径按照深度排序，那么随着深度的递增，可以和当前路径匹配的路径的深度区间左右端点是单调递增的，此时我们就可以愉快的使用单调队列。

但是复杂度分析存在一个漏洞，每次初始化的复杂度是$min(R-L,max(dep))$的其中$max(dep)$为这个联通块之前的联通块的最深深度。

所以我们可以构造一个长度为$\frac{2}{3}n$的长链，在中点处构造一个$\frac{1}{3}n$的菊花，此时我们就可以愉快的把你卡成$O(n^2logn)$

为了避免这个情况需要把联通块们按照最大深度进行排序，然后按照这个顺序插入路径，关于同一个深度的路径，我们使用以深度为下标的数组存储路径的带权长度

预处理一下点分树就可以了。

长链剖分

设$f_{i,j}$表示以$i$为根的子树，往下走$j$条边的最大权值和，考虑长链剖分优化，

然而因为统计答案时要把每个长度的答案都找一遍，复杂度 $O(n^2)$，并没有优化的效果，所以我们可以开一颗线段树，像树链剖分那样，用线段树维护长链剖分。

虚树消耗战

虚树只维护有用点和维持有用点的祖先后代关系，可以用单调栈算法得到。

对于每一次使用机器，建立维护资源点的虚树，用树形$DP$求解，其实可以在第一次$dfs$就对每一个点预处理出割去这个点所需要的最小代价。

然后对于虚树，正常跑树形$DP$即可。

虚树世界树

每次对于临时议事处建立虚树，本题要计算整棵树的答案，将贡献拆为两部分：

1. 虚树上的点对答案的贡献，
   设 $f1_x$ 为离 $x$ 最近的点的编号，树形换根求出。

2. 不在虚树上的点对答案的贡献。

我们又可把这些节点分为两类：

• 虚树上某个节点的儿子的不在虚树上的子树，
  显然这类的管辖结点很好找，但是计算大小细节。

• 虚树上某两个节点 u,v 之间的点的子树内的且不在虚树上的节点
  按照管辖结点继续分为都被一类点管辖和被两类点管辖来处理。

寿司晚宴

让甲乙选的数字的质因数集合没有交集就可以了。

当 $n <= 30$，对于每个$2-n$分解质因数，把每个质因数是否出现状压起来存下来，$dp$的时候从前往后扫。

当 $n <= 500$，显然的根号分治，一个小于500的数，最多只可能有1个比22大的质因子。

我们可以将$2-n$按大质因子大小排序，这样令大质因子相同的数排在一起（也就是不能甲乙同时选的）。

当你发现有题（无关顺序，排序对其无影响）做不动时，排序永远是你最坚强的后盾（无论是 dp 还是贪心，排序可以让 dp 更快）

对于每一段大质因子相同的数，我们在这一段开始的时候把dp的值赋给f1数组和f2数组（就是第一个第二个人获得了当前的大质因子），然后在这一段内部用刷表法推f1和f2。

最后容斥一下就可以了，很好想。

围豆豆

状压$bfs$，考虑什么时候会将豆子围起来，可以按照数组定义、围住判断、由上一个格子的状态$ms$推出下一个格子的状态$ns$、通过什么来算出$f$数组的线性顺序思考。

豆子的总价值减去路程上的花费得出来的结果，最后再取一个最大值显然是我们想要的答案。

具体看题解。