mygr main()

[[点分治]] LCA 来自异象石的小 Trick 对于一个点列 $a_i$ ，将其按照 $dfs$ 序排序得到 $b_i$ 那么有 $dep_{Lca(b_l,b_{l+1}…b_r)}=\min_{i=l+1}^{r} dep_{Lca(b_i,b_{i-1})}$ 一个点与另外一个点的 LCA 一定位于其祖先节点中，所以在 “找点对的LCA” 的问题中可以固定一个点，查看这个点的所有祖先的贡献 [[ 测试讲评&习题（二）.pdf | HDU6031，练习题第二题 ]] Trick 如何判断是否为 一棵树，同时满足无环(LCT/并查集)与点数-边数=1 给出一个树上的点集，问该集合中所有点中的最优点，且所有点只会 整体 向上跳时，若任意一点作为根的子树中的点一定不优时，则可以将这部分点剔除出，剩余点跳跃是均摊 $O(n)$ 的 # P6779 rla1rmdq 对于树上多条路径，找其中两条使得其的交…的问题，可以考虑树链剖分，在每条链上考虑经过这条链的路径在这段上的贡献 # Iron Man

点分治 边分治 对边分治无用论的一记 重拳 边分的好处就在于只需要处理边两端子树的情况，而并不需要考虑多子树的合并问题

概率是顺推，而期望需要逆推 连续型期望 Random Max 转换Trick 对于求期望的问题，可以转换为求每个代价出现的概率乘上代价的和 对于状态设计转移阶段较为麻烦的题目，可以考虑爆列每个状态的转移，然后跑高斯消元 对于高消观察它的图上性质，树形结构可以考虑自下而上的消元

相关链接：[[BSET定理]] 给无向边定向，形成一种方案，当遇见 “决策二选一” + “ 决策结束后某些位置必须为 $\frac{1}{2}$ ” 的问题，往往就是他没错了 有时候可以配合分治，将边的方向的定义变为 “是否与右侧交换”，来得到最终答案 # Balance 若题目条件并非 “一定为 $\frac{1}{2}$” ，而是 “差值不能超过 1” ，可以考虑建一个超级源点再连上一条边，表示差值

当涉及到可能存在不优的操作撤回/反悔到其他决策，且决策点影响范围不大（或者总结就是可以通过图论建模网络流建模得出）时，可以考虑模拟费用流去解决问题 其实算法流程就是数据结构（或其他）去优化每条流的退流，增广的过程，根据网络流的相关知识可以得出，在残量网络上跑单条流的增广过程，所影响的流量此时是 $O(1)$ 的，通过数据结构将增广过程的 $O(n)$ 优化 模板题：[[P4694 PA 2013 Raper]]

要点：画出分治中心，考虑一个子树内的询问如何计算得到其他子树内部的答案 即可 关于其他子树：两种方法，一种是容斥减去，若没有可减性则考虑前后缀合并 # 树上游戏 # 树的难题

对于无后效性的序列递推，或者状态数较少的最优性 dp，考虑矩阵快速幂解决 Trick 分段矩阵快速幂，时间复杂度不会有很大的变化 Odd Steps，当分段处理相同的矩阵的乘法时，尝试预处理 $2$ 的次幂，这样子矩阵乘法时就可以省掉一个 $n$ (因为只需要处理一个行向量与一个矩阵的乘积) 老八 优化矩阵乘法的取模，可以考虑用一个int128的数组来存，计算完后统一取模 可以尝试用矩阵乘法来更简单的实现区间历史和

基础 设一个无向图 $G$ 的邻接矩阵为 $A$ ，度数矩阵为 $D$ 则其的基尔霍夫为 $K=D-A$ 将基尔霍夫矩阵去掉一行一列，则无向图 $G$ 的生成树数量为 $det(K’)$ 有向图 对于有向图，我们则求的是它的内向生成树与外向生成树数量 对于内向生成树，则度数矩阵为节点的出度 对于外向生成树，则度数矩阵为节点的入度 例题： # 黑暗中的幻想乡

Trick 当需要预处理且卡空间时，可以考虑将状压数组滚动，按照 popcount 的大小去分割，空间复杂度 $O(C_{n}^{\frac{n}{2}})$ # 信号传递 当查询序列方案数，且序列是否合法只需要判断相邻两个元素时，可以考虑状压一个三进制数组表示某个元素 左右都没安排元素/左右有一侧安排了元素/左右都安排了元素 的方案数