trick

· · 个人记录

考前必看

2.dev c++编译命令

 g++ -Wall -c -std=c++14 -O2 -Wextra -Werror -fsanitize=address,undefined

3.注意事项

4.对拍

线性基

那种不会修改并经常调用的值一定要用 const。

二分图的最小边染色结果等于点的最大度数。例题

gcd(a,b)=gcd(a+k×b,b)

算 K4 的个数。首先使用一种处理无向图的经典方法：将所有点按度数从小到大重标号，考虑一 个点有多少大于它的与之相连

线段树优化建图

若 p 与 n 互质，则在 k∈{0,1,…,n−1} 时，k 不同时 k⋅pmod  n 的值也不同。

lca 性质

定义 lca (S) 为集合 S 中所有元素的最近公共祖先。

lca(S)=lca(mindfn(S),maxdfn(S))，证明不难通过 1.3 中的结论得到，可用于优化子集的 LCA。

lca(S∪T)=lca(lca(S),lca(T))，证明显然，是很多性质的基础。

x 到 y 在树上的简单路径可以分为 lca(x,y) 与 x 的链与 lca(x,y) 与 y 的链，证明：显然一定会经过 lca(x,y)，而如果经过 falca(x,y)​，则不为简单路径。

lca(x⋯y)=mindep(lca(x,x+1),lca(x+1,x+2)⋯lca(y−1,y))，证明基于虚树。

若树上 x,y 的简单路径与 a,b 的简单路径相交，则 lca(x,y) 在 a,b 的简单路径上（或反过来）

1，启发式分裂

分治时过程中分成大区间和小区间，每次只用小区间的长度去搞大 & 小区间。

时间复杂度为 O(n\log{n})。

近乎模板

2，反悔贪心

这一类题目通常直接选最值不一定最后最优，而用动态规划的算法时间复杂度不允许，我们可以考虑一种可以反悔的贪心。反悔贪心的关键在于找到反悔的机制，通常为考虑选一个数后（通常为最值）若不选其则可能会有哪些其他答案加入候选集合。一般都考虑用堆和链表来实现。

模板题

3，若干源最短路

如果需要求若干源之间的最短路，可以通过分组的方式来求，分成两组，对于每一组分别建一个超级源点和超级汇点，然后可以计算。可是组内无法计算。如果继续分治做的话时间复杂度是 O(nm\log{n}) 等于没有优化，考虑按每个二级制位分成两组，那么两个不同的数必有一位不同则可以在 O(m\log^2{n}) 的时间复杂度内解决。

[GXOI / GZOI2019] 旅行者

分层图最短路也不能忘

4，不等式

对于有序数组 \{a\} 和 \{b\}，

对正数数组 $\{a\}$，$\frac{\sum_{i=1}^na_i}{n} \ge \sqrt[n]{\Pi_{i=1}^{n}a_i} (\sum_{i=1}^{n}a_i^2)(\sum_{i=1}^{n}b_i^2) \ge (\sum_{i=1}^{n}a_ib_i)^2

应用很多

5，k 小子序列

如果全是正数，那么先从小到大排序，定义一个状态 (pos,val) 表示前 pos 个然后 pos 必须选，值为 val，可以扩展到 (pos+1,val+a[pos+1]) 或 (pos+1,val-a[pos]+a[pos+1])，即 pos 选与不选。为什么这么定义状态？如果定义 pos 不一定选的话更新有可能会造成以前已经有过的状态（这里真实的状态是哪些选了，哪些没选），所以规定 pos 一定要选。每次取出最小的扩展，再放进小根堆里，扩展 k 次就可以得到答案。

如果有负数，先将所有负数加起来，这是最小的答案，然后所有负数取反再求一遍 k-1 小子序列加到前面的负数的和里即可。

9，当总情况数不多时可以考虑枚举所有情况

UMNOZAK

CF1400F

10，对于一些树上的问题如果有一个特殊点则可以考虑把这个点当成根来处理。

山谷

11，尺取法。在 CF 上叫 two pointer，其实就是两个指针在那跑。通常用来优化具有单调性的题目，可以把二分的 \log 给优化掉。

[NOI2016] 区间

12，对于两个单调性不同的函数取 \min,\max 的结果通常是一个凸函数，可以三分或者二分那个交点。

冰火战士 [CEOI2017]Sure Bet

13，一些删除操作的题可以考虑离线倒序变加入，而一些正面不好考虑题的可以考虑从反面考虑。

14，看到有两种取值方案就往 2-sat 上去想，不过双向边的 2-sat 可以用并查集的扩展域来做。

15，大模拟要一句一句对着写，尽量写之前先把细节想好，而且不要用大量的 if else 最好先写一个数组预处理。

16，线段树上二分和树状数组上倍增都可以做全局第 k 大或者 lower_bound，这种时候就不要写平衡树了。

17，一些交换相邻数而达到某种条件的题的通用方法是重新排列然后求逆序对数。

18，函数传参也需时间，不要传一个大数组进去。

19，对于搜索的一些优化：

  1. 记忆化搜索可以剪掉大部分的复杂度

  2. 一些剪枝（可行性，最优性，冗余性）也是很有效的

  3. 提前预处理出一部分也是一个大剪枝

  4. 双向搜索可以使复杂度直接开根号，折半搜索直接取对数 \

20，在做 FMT 的时候对于或运算是做子集和，对于与运算是做超集和，可以考虑用 FMT 做计数。

例子：CF449D Jzzhu and Numbers

21，曼哈顿距离切比雪夫距离相互转换：曼哈顿转切比雪夫 (x,y)\rightarrow (x+y,x-y)，切比雪夫转曼哈顿：(x,y)\rightarrow (\frac{x+y}{2},\frac{x-y}{2})

22，考虑对于一个坐标求到他切比雪夫距离不超过某个 k 的范围是一个矩形，对于曼哈顿距离是一个菱形，所以这种问题一般考虑转成切比雪夫距离。

23，如果是求距离的最值时曼哈顿距离可以拆绝对值。

24，列式子的时候要尽量列常数因为这样可以减少复杂度。

25，动态规划问题找子状态时可以考虑题目的问题，对问题进行组合（或者多一个问多一维状态），最后再对状态进行化简。

26，有的时候我们不仅要考虑多项式的值，还要考虑其本质（即定义式），因为对于不同的自变量定义式的系数是不会变的，这样有时在推式子的时候就可以把其提到前面来。

27，要注意观察式子的形式，如果发现已经是一个积性函数后就可以考虑直接求了，常见的积性函数就：欧拉函数，莫比乌斯函数，约数个数函数，约数和函数，常函数，恒等函数，单位函数以及它们的幂次。

28，对于一个 dp 式如果某一维特别大则可以考虑矩阵快速幂（转移可以写成矩阵）或拉格朗日插值（最后的值是一个多项式）来优化。

29，可以通过预处理最小质因子做到：O(V)-O(\log{V}) 的质因数分解，其中 V 是值域。考虑每次直接除最小质因子，而把所有质因子放缩成 2 则除的次数绝对不会超过 \log{V} 次。

30，树形 dp 时状态还可与子树内的边有关，即可以将边转换为点。

31，对于统计满足某种条件的区间个数或者计算区间个贡献时可以考虑 cdq 分治计算左端点对右端点的贡献。

32，最小不相交路径覆盖 = 原图节点数 - 新图最大匹配（a->b,a1->b2），如果相交就传递闭包。

33，最多不相交路径：每个点只属于一条路径 \rightarrow 每个点拆成两个点，若 u\rightarrow v 则连一条 v_2\rightarrow u_2。

34，当问题中出现一种冲突时，就可以采用最大权闭合子图。具体来说，对于一个事件，只能得到 a 收益和 b 收益之中的一种。我们就把 a 收益作为正权点，b 收益作为负权点，跑最大权闭合子图

36，对于一个排列会有很多个置换环，如果有一个置换是 i\rightarrow p_i，那么一定是在这个环上。

37，有的时候不拆式子比拆式子更容易得到解法。

38，很多期望的递推式没有无后效性的，所以不要局限在这里了。

39，有的时候问题可能就是个结论，而不用算法去求得答案。

40，在做构造题的时候可以先考虑求出上下界然后再调整求出构造方案。

41，如果一个 x\le y\le x+1 那么可以把 y 压成一个 01 串。

42，对于要求对每个 i\in[1,n] 的数都求答案时可以考虑从 i 扩展到 i+1。

43，做题时可以先想一想暴力怎么做，然后再优化。

44，看见 ax+b\bmod c,a\in[0,t] 这种形式往循环节上去想。

45，对于数线段题，可以先枚举端点，再枚举之间的点。

46，对于一些 \sum 式（或 \prod），我们可以直接把其设为一个函数然后求解，不要局限在某种方法上了。

47，很多数区间题也是先枚举两个端点，然后判断中间的点。

48，从某点跳到根合并的操作，这很类似 LCT 的 access 操作，所以我们可以模拟 access。从而降低复杂度（变为均摊 \log{n}）

49，拉格朗日乘数法，对做等式约束的题目来说有很大的帮助。通常我们都会二分 \lambda。

50，\gcd(x^a-1,x^b,-1)=x^{\gcd(a,b)}-1

52，比较难搞的东西可以想想分治，然后考虑怎么分。

53，有向图邻接矩阵的 k 次幂即为两点间长度为 k 的路径条数。

54，\frac{x}{y} 是 k 进制下循环小数当且仅当 (x,y)=1\and (y,k)=1

55，圆计数先考虑特殊位置然后拆成序列计数

66，如果有题要求恰好选 k 个时的最值可以考虑 wqs 二分（凸性直接不管）

67，如果一些函数最多只有一个交点就可以维护那个交点于是就有了一点单调性（或者直接 EI tree？）

68，一下看起来条件很多的诈骗题往往有用的东西没多少。

69，a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b

70，k \max (S)=\sum\limits_{T\subseteq S}{|T-1|\choose k-1}(-1)^{|T|-k}\min(T)

71，实链剖分可以用区间染色来做，也就是可以树剖线段树

72，质数有关题优先考虑 2,5

73，偶加奇减考虑系数 (-1)^{x}，然后考虑行列式等东西。

74，绝对值加减可以拆成一些东西取 \max。

75，线性基的性质

76，当某些东西范围很小的时候可以考虑状压或虚树

77，有关子集的转移都可以考虑从 lowbit 转移减少复杂度。

78，两棵树合并后的新直径的端点一定在原先两棵树的两个端点中。

79，复杂度为 \max (\frac{n}{x},x) 的东西考虑根号分治。

80，树上数颜色可以考虑对每种颜色建虚树。

90，想要序列相邻两项的 lca 的深度尽量小，选带权重心当根！

91，平面上的问题先想想能不能转成 1 维，再想想两维是不是互不相关（即可以分开做）。

92，一种特殊的分治？按二进制某一为是否为 1 分治，这样任意两个不同的数还是可以计算贡献的。

93，当我们发现一个 dp 的一维是一个多项式的时候，我们可以考虑用点值表示，最后再插值回去，因为点值乘法是 O(n) 的，而系数卷积是 O(n^2) 的。

94，从 [1,n] 中选一个集合使其和为 s。直接贪心选一段后缀以及前面的一个数即可。

95，a+b=a\text{ and }b+a\text{ or }b。

96，一个经典集合容斥：f(S)=\sum_{T\subseteq S}\sum_{T'\subseteq T}(-1)^{|T|-|T'|}f(T')。

97，看到类似 LCT 的 access 操作可以想想时间戳或者直接 LCT。

98，有的时候一堆乘法可以考虑取 \log，比如组合数比大小的时候，取 \log 不影响大小关系，又可以化乘为加。

99，如果看到要求某个不能化简的函数的非精确值，考虑泰勒展开取前几项。

100，\mathcal{X}\ge \mathcal{Y} 计数的时候可以考虑差分，\mathcal{X}=\mathcal{Y} 计数的时候可以考虑前缀和。

101，看到有凸性的问题想 wqs 二分，不需要在意是否有“刚好取 k 个”的字眼，或者看到凸性就想办法找这些字眼。最小生成树可以写成拟阵是凸的。

102，对于 n-1 次多项式 f(x)=\sum_{i=0}^{n-1}a_ix^i 模 x^m-1，对于 x_0，当且仅当 a_i 都等于 x_0-1 或 -(x_0+1) 或 0 时为 0。

103，a<b<c,\min(a\bigoplus b,b\bigoplus c)<a\bigoplus c

104，格点凸包大小是 O(n^{2/3}) 的。

105，平面随机游走的期望最远距离是 \sqrt{n} 的。

106，\sum_{i=1}^{n}\sum_{j=1}^{n/i}n/(ij)=O(n\log n)。

凸多边形，经过每个点一次的最短路径绝对不会出现交叉，可以用区间 dp 解决 P9119

求解组合数在 % p 意义下，若 p 不是质数，先筛出质数再约分 P3200

当求解组合数时 n,m 远大于 p 考虑用卢卡斯定理求解

图论：记得考虑反向建图

杂项： 关注每个点的最短路，那么肯定是要先将图分层 树上边权转点权转移到儿子节点，但是特别注意多余信息处理（尤其是树剖的时候）

比如树剖结束的时候处理最后一条重链，最顶端节点的答案不能处理进去（因为会有多余信息 (t o p x , f a t o p x) (top_x,fa_{top_x}) (topx​,fatopx​​)）

还有一些计数题比如说统计路径上有多少个不同颜色的，注意一下根节点的多余数据处理（因为根节点是没有颜色的）。

看到图论题先想一下这几个问题：图是否连通？有向图还是无向图？是否带权？有没有重边与自环？

遇到矩阵问题不要老是想和矩阵有关的算法，有些时候或许只是道简单的图论。可能每个点是一个点，也可能一列一行是一个点，都有可能。

看清楚是有向图还是无向图，无向图空间要开 2 倍！网络流的边数与点数不能算错！

缩点的时候注意不能将原图和新图搞错。

如果需要使用各种 连通块内的算法（比如最短路，网络流等等），无论图是否连通，最好建立 虚拟起点 / 虚拟终点（网络流有个词叫 超源超汇），强制使这张图变为连通图。

无论做什么题目，如果需要建图，一定要注意 边权是否有意义！

比如说 P3275 [SCOI2011] 糖果，利用差分约束建图时，如果采用最短路建图，就会出现 (b , a , − 1) 这样的边，但是糖果数显然非负，因此边权无意义，答案错误。

树的直径有一个很好的性质：

如果一棵树的直径长度为偶数，那么这棵树的所有直径一定交于一点，并且这个点是直径的中点；

如果一棵树的直径长度为奇数，那么这棵树的所有直径一定交于一边，并且这条边的中点是直径的中点。

求点双连通分量栈中仍然可以存点，圆方树维护起来很方便。

无向图中最大值最小的路径一定在最小生成树上
合并两个连通块的直径，直接比较四个端点两两连起来的长度即可。

一些有代价的完美覆盖问题，选格子有行列限制有代价/收益的题往往考虑网络流。

如果遇到n3的转移矩阵，但是我们一次只想知道的结果是一维的（即暴力乘的复杂度是n2），那么可以考虑倍增预处理转移矩阵的幂，求出转移矩阵20,21,22...次的结果。询问的时候只需要n2log而不是n3log，预处理则是n3log，总的复杂度就可以变成q∗n2log+n3log

DP时，如果状态很大，结果很小，可以考虑能否将结果与状态互换。

涉及网格图带权，行列选择限制/覆盖一类的问题，可以考虑网络流。

一个经典问题：有一个序列，给出若干个区间，问有多少种选法使得选出的区间能覆盖整个序列。 我们考虑容斥，显然容斥系数是(-1)^强制不覆盖的位置个数，记f[i]为前i个位置都已经确定了,第i个位置不选的方案数和，它可以从f[j]∗(−1)∗2k

转移而来，我们把所有区间挂在右端点，从左到右扫的时候做区间乘法即可。

网络流：

网络流中拆点是很常见的一种技巧。P1251。

网络流中计算点数的时候注意不要忘记 拆出来的点与超源超汇，在采用当前弧优化的时候这些点也是需要算进去的。

网络流中出现阶段性问题的时候（比如时间），一般就是分层图上的网络流问题，此时算好 点数与边数的极限上界，并且不要采用 ISAP 求解最大流（直接二分答案除外），因为 dinic 可以直接在新图的残量网络上跑。P2754。

数据结构：

数据结构题不要只想 log ⁡ 结构，分块它不香吗？根号分治它不香吗？ 莫队它不香吗？

有些 DS 题会问你一个区间 [l,r] 内需要划分成至少几个子序列以满足题意，CF1516D，这个时候有一种思路就是先双指针处理出每个点往右边能够预处理的最右点，然后倍增即可。

FHQ Treap 在处理区间信息的时候如果需要维护懒标记的时候需要注意 Merge() 函数中 x,y 都需要下传懒标记。P2042。

在维护树上路径时，如果只是点的独立的加减，可以考虑用括号序来维护（拆成两部分）

需要求树上很多路径中 k 近 / 距离和 一类，考虑点分治 / 在点分树上解决。

子树求和可以转化为 DFS 序上区间求和 树状数组可以区间查询 / 修改（差分）

需要查询序列上区间数据结构，只要满足总和是可以接受的范围，可以用线段树，每个区间维护一个这样的数据结构（例如 AC 自动机等）

多维偏序问题，排序可以降维，CDQ 分治可以降维，剩下只需要树状数组 / 线段树

树上连通块有概率出现，再加上和的次方，往往可以拆开来，变成任意选 K 个可重，有序的点，考虑贡献。

当又需要分块，每个块维护数据结构时，块的大小考虑调整（不再一定是√n）（平衡规划）

同理，对于图论中度数总和固定、多组询问查询的点数固定，查询点需要枚举出边，但可能一直查询度数比较大的点。此时考虑平衡规划。（询问点个数 / 度数 大于 / 小于√n 分开来做）

对于点分治时两个不同的子树的结果混在一起需要判掉，可以考虑几种办法：

在点分树上儿子记录当前点分树子树中的节点到父亲的结果，计算父亲时在这里减去。

维护DFS序，两个子树对应两个无交的区间，可以考虑区间分裂一类的做法。

对于有很多颜色的点，需要对相同颜色计算影响，可以把每个颜色拉出来在 DFS 序上搞事情（相邻 + 1，lca-1 一类）

如果又加上了深度限制，那么相当于除了 DFS 序这一维，还多出了深度这一维，可以考虑（主席树 / CDQ 分治 / 二维数据结构）

对于这样一类问题：每个元素（边 / 点之类）具有权值 / 权值范围，每次只需要考虑权值是一定值 / 一定范围的元素的影响，可以考虑建立权值线段树，将元素的影响挂在线段树对应的所有区间上，查询就查询区间。

当需要查询树上是否存在一条路径过两个点时，可以将路径端点记在 DFS 序上，然后两点子树查询，这就变成了两个区间数点的问题（二维偏序 / 扫描线 / DFS 动态树状数组维护增量）

需要维护序列轮转问题时，不一定非要 splay，如果轮转很特殊时可以采用线段树 + 预留空位的形式转化为单点修改。

想要存储很多东西的 0/1 状态，且需要支持 xor/or/and 等操作时，bitset 是个非常好的选择（计算复杂度可以除以 32），别忘了 bitset 还有左移右移操作，可以用来处理 + 或 - 替罪羊树跑的很快。

带旋转的平衡树是很难在内层套上线段树的，所以平衡树套线段树应考虑替罪羊树或 treap

一堆操作 + 询问的题，如果很容易处理一堆操作对一堆询问的贡献，可以考虑分治，你可以考虑权值 / 时间分治

一棵 Trie 如果要维护 + 1 异或，那么不妨从低位到高位建 Trie

线段树分治往往应用在一些对象知道插入和删除时间时，维护合法情况很容易，但撤销非法情况比较困难时。

要算一个点和一堆点的距离的时候，可以考虑将距离拆成两点深度和 - 2 * lca 深度，lca 深度可以表示成 lca 到根的节点数，那么直接树链剖分链上区间加区间求和即可。

DP： 选多个向量，并且要求 x,y 和 y / x 两两不同，并且 x，y 都有范围，可以 jiangxiang

遇到类似于 n 个东西分成两组，差最小等问题，不要总是想着一些奇奇怪怪的算法，如果就是个容量为 \dfrac {n}{2}​ 的背包问题呢？ 此时的体积和价值都是这 n 个东西的属性。

数学 / 数论： 使用费马小定理时记得判断 a 和 p 是否互质

对于一张无向图的邻接矩阵而言，如果 A_{i,j} 表示 i 与 j 之间是否有连边，那么做矩阵快速幂 A^k 之后 A_{i,j} 的值表示从 i 出发走 k 步有多少方案到 j 。

看到异或问题首先就是要想到线性基，其次就是要想到 a\oplus b=a\mid b-a&b，因为这样就可以通过处理线性基 / 或 + 与的手段解决异或问题。 当然不要忘记二进制问题可以拆位处理。

小技巧： 遇见对一个区间取数问题求方案数，并对 2 取模时考虑容斥拆成 1-l-1 和 1-r，贡献是 1 和 - 1，可以都按 1 算

遇到区间问题多想想差分，尤其是树上差分。 类根号分治思想真的是非常常见又好用的一种思想！

杂项

Meet in meddle，二分 / 三分，启发式合并，倍增等算法别忘了。 当遇到组数特别多时，考虑将答案全部求完 O（1） 输出答案

如果遇到异或最短路，考虑拆点为二进制下每一位， 边的个数为（nlogn） 例题：P4366

$$ C_{n}^{2}\times \frac{n!}{2} $$ 首先我们知道一个结论：Trie 的大小是：$\sum\limits_{S \not= \emptyset}(-1)^{|S|-1} \operatorname{Lcp}(S)

P13662 其中这个 \operatorname{Lcp}(S) 就是 S 集合中的所有串的 \operatorname{Lcp}。

拆了这个式子，统计每种最长公共前缀的长度的容斥系数：

\sum\limits_{k=1}^{n}k \sum\limits_{\operatorname{Lcp}(s)=k}(-1)^{|S|-1}

下文的点 1, 2, 3, 4 对应原题面中的 S, T, U, V。

直接对无向图欧拉回路计数不太好做。考虑给边定向。枚举有 i 条边是从 1 到 2 的。那么 2 \to 1 有 a - i 条边。由于这个图必须满足每个点的入度等于出度，设 j 条 2 \to 3 的边，b - j 条 3 \to 2 的边，那么我们有 a - i + j = i + b - j。解得 j = i + \frac{b - a}{2}。同理有 k = j + \frac{c - b}{2} 条 3 \to 4 的边，l = k + \frac{d - c}{2} 条 4 \to 1 的边。

这样我们就将题目的无向图转化成了有向图。在这个图上做欧拉回路计数。可以考虑 BEST 定理，有向欧拉图的本质不同欧拉回路数量（循环同构视为本质相同，每条边互相区分）为：

T \prod\limits_{i = 1}^n (out_i - 1)!

其中 T 为图的外向生成树个数（注意到有向欧拉图以每个点为根的外向生成树个数相等），out_i 为 i 点的出度。

这题要求欧拉回路从 1 出发和结束。每一条欧拉回路 1 都出现了 out_1 次，把循环同构的加上，所以答案乘上 out_1。注意这题每条同方向的边互不区分，所以答案乘上 \frac{1}{i! (a - i)! j! (b - j)! k! (c - k)! l! (d - l)!} 即可。

时间复杂度 O(a + b + c + d)。

注意判一些无解的情况，比如 i, j, k, l 不在范围内。

agc051D

发现每两个点之间都有一条边权，考虑优化建图，建立虚点（如前缀虚点和后缀虚点例子）前边数降至 O（nlogn) 或 O（n）级别

当 dp 由上一种状态转移到当前状态时，不一定要枚举所有之前的状态考虑最优的状态在哪里例子 ejoi2022

在计数时能减少取模就减少取模，取模的常数太大

遇到括号匹配问题时，可以将左括号设为 1，右括号设为 - 1，总和为 0，即为匹配成功，T3

kmp 与 border（必看）

主定理

T(N)=a \times T(N/b) +O(N^d)

1. 当 d< \log _{b}{a} 时，递归时间复杂度为：O(n^{log_{b}{a}})

2. 当 d= \log _{b}{a} 时，递归时间复杂度为：O(n^d \times \log _{}{n})

3. 当 d> \log _{b}{a} 时，递归时间复杂度为：O(n^d)

区间贪心算法总结

问题类型及解法

1. 点覆盖区间问题

2. 区间覆盖点问题

3. 最大独立集问题

4. 区间分组问题

5. A 区间覆盖 B 区间问题

6. 区间求并集问题

7. 去除包含区间问题

性质

树的重心如果不唯一，则至多有两个，且这两个重心相邻。

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。

把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离

一棵树的重心是根节点所在重链上，深度最大的满足 sz_{u}×2>sz_{root} 的点

当 \gcd(a,b)=1 时

\gcd(a^m-b^m, a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)}

成立

SOSdp，高维前缀和 dp 很常用和常见，遇到子集问题时要优先考虑

整体dp

方格中对于行与列需要满足某种特征的题面，往往可以建图来解决。

加法恒等式： a+b=a\oplus b+2\times (a\& b)

一个排列随意交换最少交换次数为：结点数n-形成的环数。

只能相邻交换为逆序对数

如果有题是把把物品分成一组一组的，或者一个物品的价值是一次函数的考虑可能最多只有一组不取满

在写欧拉回路时，一定要写当前弧优化，不写可能会被卡。例：P11762

\operatorname{mex}_{i,i\in A}=\min_{i,i\in\complement_S A}

求一个排列的所有区间的 mex 的和考虑枚举mex从小到大加入数，把只要包含加入数的极大区间的区间的个数算出来，mex是几这个区间就会被算几次，所以答案正确。

如果一个题求区间贡献和最值有关可以考虑用链表维护，从小到大加数，求完贡献后在链表上删去。

有类似于最晚在 a_{i} 时扩展考虑将 a_{i} 从小到大排序，从小到大扩展一定最优。

极小 mex 区间只有 O(n) 个。这里极小 mex 区间指区间 [l,r] 使得不存在区间 [l',r'] 满足 \text{mex}(a_{[l,r]})=\text{mex}(a_{[l',r']})。

证明：假设 [l,r] 是极小 mex 区间。l=r 的情况只有 O(1) 个，其余情况 a_l\neq a_r。分成 a_l>a_r 和 a_l<a_r 的区间，先考虑前者。由于是极小 mex 区间，故删除 l 或 r 都会使得 mex 变化，因此 \text{mex}(a_{[l,r]})>a_l>a_r。一个 l 只会对应一个 r。假设存在 r'>r 且 [l,r'] 是极小 mex 区间，并且 a_l>a_{r'}，那么 \text{mex}(a_{[l,r]})>a_{l}>a_{r'}，也就是说 a_{r'} 在 [l,r] 中已经出现过，删除 r' 不会使得 mex 变化，故 [l,r'] 不是极小 mex 区间。

数论分块不要忘：

向下取整:r=\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor } \right \rfloor 向上取整:r=\left \lfloor \frac{n-1}{\left \lfloor \frac{n+i-1}{i} \right \rfloor-1 } \right \rfloor

注意特判 n<=i 的情况

下面用组合意义证明 \sum_{i=0}^m i{2 \times n + m-i-1 \choose 2 \times n-1} = {2 \times n + m \choose 2 \times n + 1}。

式子的组合意义为：有 2 \times n + m -1 个球排成一列，选出一个长度为 i 的后缀丢掉，剩下的球中选出 2 \times n - 1 个并以 i 的系数贡献到答案中。

先将 i 的贡献摊到后缀的每个球上，组合意义改写为：选出后缀第 i 个球，将其以及后面的所有球丢掉，然后再丢掉一个任意长度（可以为空的后缀），再选出 2 \times n - 1 个球。

也就是枚举 i,j 满足 1 \leq i \leq j，丢掉长度为 j 的后缀，并给答案加上 2 \times n + m - 1 - j \choose 2 \times n - 1。

尝试把组合数用基于插板的组合意义写出来，整个式子的组合意义为：枚举 i,j 满足 1 \leq i \leq j，丢掉长度为 j 的后缀，然后把 m-j 个球排成一列，将其划分为 2 \times n 段。

算上之前枚举的 i,j，组合意义可以直接写成 m-1 个球排成一列，减一是因为后缀必须删掉一个球，将其划分为 2 \times n + 2 段，故方案数就是 {2 \times n + m \choose 2 \times n + 1}。

差值dp一个小trick

Dilworth 定理

𝑆 的宽度（最长反链长度）等于最小的链覆盖数。

考虑给一个 01 序列，每次删除掉一个数，满足删掉后的字符串是删除前的子序列，删除的方案数。考虑把 0 变为 < ,把 1 变为 > 为了保证不重不漏，每次只能删除 01 中其中一个，相当于在每两个数之前插一个时间戳，满足不等关系即可。例1，例2

边权转点权直接把边权下放到字节点即可，点权转边权考虑拆点。把一个点拆成u->v ，边权为 w。

dp计数贡献延迟计算，例题:P14364

对于一连串的取最小值，可以考虑变为二分图匹配，从小到大排序后再匹配。例题：AT_arc207_a

分块块长不一定要相等，可以按照 $1,2,4,8$ 来设置块长有时有奇效。 逆序对数的奇偶性 = ( $n$ − 置换环个数) 的奇偶性