点分治可以处理一类静态树上路径信息统计的问题。
点分治，选择一个点作为根，处理过这个根的路径，在将树分成若干子树递归的处理。
和序列的分治一样，我们希望树尽量平分，使得递归层数尽可能的小。
贪心的解决这个问题，选一个最大子树最小的点，即树的重心。这样递归的层数是 $O(\log n)$。
1 | struct LinearBase { |
1 | struct LinearBase { |
1 | LinearBase intersect(const LinearBase& A, const LinearBase& B) { |
给定带权图 $G$，求让 $k$ 个关键点联通的权值最小的子图（$1 \le k \le 10$）。
关键点的个数很少，考虑状压 $dp$。
设 $dp[mask][i]$ 表示关键点的点集 $mask$ 连到顶点 $i$ 最小权值和。
转移的时候有两种情况：
固定顶点 $i$，合并 $mask$ 的子集 $T$ 和 $T$ 的补集两个 $dp$ 状态，相当于顶点分叉。
固定点集 $mask$，顶点 $i$ 向周围的点用最短路进行转移，相当于节点向外生长。
时间复杂度：$O(3^k \cdot n+2^k \cdot m \log n)$。
给一个序列，分成恰好 $k$ 个连续段，每个连续段至少有 $m$ 个，每个段的贡献是其前 $m$ 大之和，求所有段贡献之和的最大值。
所有值拖进去排序，取前 $mk$ 大之和就是答案。
构造只需要维护哪些位置是前 $mk$ 大即可。
证明的话，考虑把除了前 $mk$ 大的元素都删除，他们的有无对于答案没有影响。
全场最难。
求十进制数 $n!$ 在 $b$ 进制下有多少个尾 $0$。
题目等价于求最大的 $x$，使得 $n! =k \cdot b^x$ 成立，等价于对 $b$ 质因数分解后的每一个素因子，$n!$ 中对应素因子的幂次与其幂次之比的最小值。
于是，我们需要计算出 $n!$ 对于一个素因子 $p$ 的幂次。
显然，$1$ 到 $n$ 中 $p$ 的倍数有 $n \over p$ 个，$p^2$ 的倍数有 $n \over p^2$ 个，又由于 $p^2$ 的倍数在前面一次已经计算过一个了，只需要加上 $n \over p^2$ 即可。以此类推，于是有
$$
\alpha=\sum {n \over p^i}
$$
注意别爆掉 $long long$。
给一个序列，一串连续的相同数字视作一个联通块，你需要先选择一个联通块，然后每次将这个联通块颜色变成另外一个以此扩大一开始的联通块，直到所有颜色都相同，求最小操作次数。
考虑 $dp[l][r][0/1]$，表示将 $[l,r]$ 区间全部变成 $l$ 处或者 $r$ 处的颜色所需要的最小操作次数。
因为只有一个起点，每次操作只需要考虑扩大一个位置即可，即 $dp[l][r][0/1]$ 只会从 $dp[l+1][r][0/1]$ 和 $dp[l][r-1][0/1]$ 转移过来。
不妨令第三个维度为 $0$，只有三种情况：
$[l+1,r]$ 全部变成 $l+1$ 处的颜色，如果 $l+1$ 和 $l$ 处颜色不同，那么需要多操作一次；
$[l+1,r]$ 全部变成 $r$ 处颜色，也是类似；
$[l,r-1]$ 全部变成 $l$ 处颜色，如果 $l$ 和 $r$ 处颜色不同，我们需要一次操作将 $[l,r-1]$ 先变成 $r$ 处的颜色，再一次操作变回 $l$ 处的颜色。
第三种情况考虑错了 T^T。
交互题，给定长度 $n$，$60$ 次询问，猜一个打乱过位置的等差数列的首项和公差，有两种询问方式：
? i：询问位置 $i$ 上的数字；
> x：询问是否有大于 $x$ 的数字。
先用 $30$ 次询问二分出最大值，然后随机取 $30$ 个位置，做差后全部 $gcd$ 起来就是公差。
随机别用 rand()， 用 mt19937。
给一个序列 $a$，其中 $1 \le a_i \le 300$，维护区间乘，询问区间乘的欧拉函数。
线段树裸题（误。
由于小于 $300$ 的素数只有 $62$ 个，欧拉函数算的时候只和乘积后的值以及这个值有哪些素因子有关。
因此只需要用 bitset 维护有哪些素因子，线段树维护乘法即可。
给一个无向图，每个顶点本身有一个颜色 $a_i$，现在要给所有顶点分别染色，满足一个联通块内的顶点染的颜色必须相同。
对于每条边，分别询问删除这条边后，最多有多少顶点染的颜色和其本来的颜色相同。
$$
1 \le n,m,a_i \le 10^5, \sum n, \sum m \le 10^6
$$
在一个联通块内，如果这条边在一个环内，删除这条边后，原联通块仍然联通。只有对于桥边，删除后会变成两个联通块，才会对答案有影响。
因此，首先需要用边双联通分量缩点，形成一个森林。
对于，森林内的每棵树，我们需要计算删除每一条树边后，子树内和子树外出现次数最多的次数，加上森林内其他树的答案即可。
对于子树内的众数，这是树上启发式合并，同样对于子树外的众数，反过来维护即可。
修改和查询最大值时，复杂度需要 $O(1)$。这里因为修改都是 $+1$ 或 $-1$，因此维护每种出现次数的个数即可。
注意：树上启发式合并时，缩点大小最好设置为对应块的大小。
场外云选手，全程智障。
数据范围小，快速幂随便搞一下。
有一段长度为 $m$ 的序列，其中一些位置坏掉了，现在可以用最多 $k$ 个线段覆盖这些坏掉的位置，求最小的覆盖线段总长度。
考虑反面，用 $k$ 段覆盖这些位置，等价于将 $n-k$ 个坏掉位置合并，合并后变成 $k$ 个连续段。
差分一下，拖出来排序，取前 $n-k$ 个。
云选手以为要二分，显然有单调性，但是并不能贪心构造。
求 $f(a)=\max_{0 < b < a} \gcd(a \oplus b, a \text{&} b)$。
考虑 $a$ 的二进制表示，如果里面有 $0$，那么 $b$ 相应位置设为 $1$，这样 $a \text{&} b$ 为 $0$， $a \oplus b$ 为 $2^k-1$，显然最大。
所有只需要考虑 $a=2^k-1$ 的情况，只有 $25$ 种，打个表即可。
给定一个序列 $a$，$1 \le a_i \le m$，将序列内元素组成一些三元组，满足三元组三个元素为三个连续整数或三个相同整数，求最大能组成多少三元组。
设 $dp[i][j][k]$ 表示考虑到 $i$ 个位置，以第 $i$ 个位置为首组成 $j$ 个连续三元组，第 $i-1$ 个位置为首组成 $k$ 个连续三元组。
然后，观察到组成 $j+3$ 个连续三元组实际上和组成 $j$ 个连续三元组等价，因为可以把横行变成竖列，数目相同，因此只需要考虑 $0 \le j<3, 0 \le k<3$。
转移方程
$$
dp[i][j][k]=\max(dp[i][j][k], dp[i-1][k][h]+{(cnt[i]-j-k-h) \over 3}+j), j+k+h \le cnt[i]
$$
云选手没注意到这个结论。
给定一个序列 $c$，每次操作可以选择除了首尾的一个位置 $i$，执行
$$
c_i=c_{i-1}+c_{i+1}-c_i
$$
判断一下 $c$ 通过这样的操作变成 $t$。
注意到每次这个操作，实际上是交换了左右的差分值，因此只需要判断 $c,t$ 的差分数组排完序是否相同即可。
注意特判首尾位置。
云选手以为要大讨论。
顶点编号按照 $dfs$ 序给出一棵带边权的有根树，每次在编号 $[l,r]$ 范围内，询问距离顶点 $v$ 最近的叶子的距离。
离线所有询问，$dfs$ 到一棵子树的时候，相当于子树内所有叶子的距离减去这条边的长度，子树外所有叶子的距离加上这条边的长度，线段树维护即可。
裸题没人做是什么情况？
给一个序列，你有 $m$ 次操作，每次操作可以选择删除一个数或者给某一个数 $+1$，但是一个数最多被加 $k$ 次，要求序列平均值的最大值。
显然，排个序，枚举删除了多少个，剩下的全部都是加到后面即可。
注意，加到哪个数并不重要，总量不超过上限即可。
Hackforces，插了 $5$ 个，最后又 FST 了上千个2333。
一排长度为 $2^n$ 的位置，某些位置上有人占领（一个位置可以被多人占领），现在你要毁灭整个区间，你有两种毁灭方式：
求最小花费。
直接根据题意模拟分治过程即可。
关键是要询问一个区间内的人数，对所有人的位置排序，询问时做两次二分即可。
分治时，注意两个细节：
第二点 $wa$ 了一年 T^T。
给一棵无根树，现在有 $q$ 次询问，每次询问无根树以 $r$ 为根时，有 $k$ 个关键点，将关键点分为最多 $m$ 块，要求满足每块内没有点对互为这棵有根树上的子孙，求这样的分块方案。
其中 $n, q,\sum k \le 1e5,m\le300$。
首先，考虑根固定为 $1$ 的做法，将关键点按照 $dfs$ 序排序，设 $h[i]$ 表示关键内是 $i$ 的祖先节点的个数，$dp[i][j]$ 表示前 $i$ 个点分成 $j$ 块的方案数，有转移方程
$$
dp[i][j]=dp[i-1][j-1]+(j-h[i])dp[i-1]j
$$
因此，对于每个关键点，我们只需要知道有多少关键点是它的祖先即可，这部分可以搞出 $dfs$ 序，在树状数组上差分即可。
之后，我们考虑这个 $dp$ 的正确性条件，必须满足计算 $i$ 的 $dp$ 状态时，他的祖先必须全部都计算过了。然后，这个条件实际上不需要用 $dfs$ 序来排序，可以考虑用深度或者说祖先的个数来排序，按照这个顺序 $dp$ 即可。
最后，我们考虑换根操作，换根后我们实质上是询问了，某个关键点到根的路径上出现了多少关键点，这个部分用 $LCA$ 差分即可。
好！