重链

1、重儿子：一个节点的最重的儿子，即 size 最大(子树大小最大)的儿子。一个节点至多有一个重儿子，其余都是轻儿子
2、重链：从某个节点开始，一直走重儿子得到的一条链，称为重链。一张图中可能有多条重链，树上的一条简单路径，至多经过 $\log n$ 条重链
3、链顶(顶)：一条重链中深度最小的节点，称为链顶，通常直接称为顶
4、如下图，图中节点旁的数字表示节点的 size，标记红色点为顶，红色边连接的路径为一条重链，单独的顶也是一条重链

差分约束

1、差分约束：有 $T$ 组样例($T \leq 10^3$)，对于每组样例，给定 $n$ 和 $m$ ($n,m \leq 5 \times 10^3$)，表示有 $n$ 个未知量和一个大小为 $m$ 的不等式组。对于 $m$ 个不等式，输入 $1\ i\ j\ z$ 表示 $x_i \leq x_j + z$，输入 $2\ i\ j\ z$ 表示 $x_i \geq x_j + z$，输入 $3\ i\ j$ 表示 $x_i = x_j$。需要判断不等式组是否存在一组未知量可以作为解，存在输出 $YES$ 否则输出 $NO$
2、差分约束系统是一种特殊的，形如 $x_i - x_j \leq c_k$ 的 $n$ 元一次不等式组，其每一个约束条件都可以变形为 $x_i \leq x_j + c_k$。观察变形后的约束条件，很接近先前单源最短路的松弛操作后保证的状态 $d[y] \leq d[x] + w$ (三角形不等式)，不妨把每个解 $x_i$ 看作图中一个点，对应地从节点 $j$ 向 $i$ 连一条长度为 $z$ 的边(将约束条件转换成图)，如果在这样的图上跑完了最短路，则一定保证约束条件满足。即，求 $x_i$ 的一组解等价于在图上求一组最短距离 $d[]$ (即 $x_i = d[i]$)，如果这样的图存在，即 $d[]$ 存在且合法(没有负环)，说明存在至少一组解
3、实现时，最短路需要一个起点，但因为无法保证整个图连通，则以任意点作为起点都不能保证得到到所有点的最短路，所以需要构建一个虚拟源点 $0$ 作为起点且到所有点距离为 $0$，将整个图连通。对于题面给出的第一种不等式，是与约束条件相同的形式；对于第二种不等式应将 $\geq$ 式转换成 $\leq$ 式，即 $x_j \leq x_i - z$，边权为 $-z$；对于第三种等式，可以相似地转换成 $x_i \leq x_j + 0$ 且 $x_j \leq x_i + 0$，即 $x_i, x_j$ 点双向连通且边权为 $0$。此处的连边规则在下面的补充处另有详细说明，并非一定移项成这种形式
4、对于最短路的实现，由于存在负权边且需要判断负环，所以用 Bellman-Ford 或 SPFA，注意由于多加了一个虚拟源点，因此 SPFA 判断是否负环的条件要修改为 ++cnt[y] > n 或 ++cnt[y] >= n + 1(Bellman-Ford 也同理需要多松弛一次)
5、运行后，$d[]$ 的值就是 $x$ 的一组解。容易发现，这组解同时增减相同的值 $a$ 后也仍是一组解，因为有 $(x_i + a) - (x_j + a) = x_i - x_j \leq c_k$，增减的值在约束条件中会被抵消

倍增 LCA

1、LCA：输入树的节点个数 $n$，这棵树以节点 $1$ 为根，接下来 $n-1$ 行，分别输入节点 $2 \to n$ 的父节点，再输入询问次数 $q$，每个询问给出两个整数 $u, v$，输出 $u, v$ 的最近公共祖先 $lca(u,v)$
2、最近公共祖先 LCA：深度最大的公共祖先，即几个节点的父节点链从下向上最早相交的点 (可以是这两个点中的一个)。性质：$u \to v$ 的简单路径可以分为两条链，即 $u \to lca(u,v)$ 和 $lca(u,v) \to v$；类似于 $max, min, gcd$ 等运算，其满足 $lca(x,y,z) = lca(x,lca(y,z))$；多个点的 $lca(x_1,x_2,\ldots,x_k)$ 等价于 DFS 序最小点 和 DFS 序最大点的 $lca$
3、倍增 LCA：类似于 ST 表，我们令 $fa[x][j]$ 表示节点 $x$ 向上走 $2^j$ 所到达的点，例如对于节点 $x$，其向上第一个父节点为 $fa[x][0]$，第二个为 $fa[x][1]$，第四个为 $fa[x][2]$，第八个为 $fa[x][3]$；此外，从根开始以节点深度从上到下标记层次，用 $dep[x]$ 记录 $x$ 的深度。这样的结构可以实现快速跳跃，要从 $x$ 向上跳跃到目标层次，可以贪心地先迈大步再迈小步：从大到小枚举 $j$，再检查 $fa[x][j]$ 是否超过目标层次，超过则不操作，不超过则 $x$ 跳跃到当前 $fa[x][j]$，继续向下枚举。例如，如果要从第 $8$ 层跳跃到第 $2$ 层，二者相隔 $6$ 个节点：为方便，从 $j = 3$ 开始枚举，此时 $fa[x][j]$ 是向上 $8$ 个节点的位置，超出目标范围不操作；继续枚举 $j = 2$，此时 $fa[x][j]$ 为向上 $4$ 个节点的位置，令 $x$ 跳到该位置，此时还差 $2$ 个节点到目标；继续枚举 $j = 1$，$x$ 跳到当前 $fa[x][j]$ 到达目标节点。可以发现，起始相隔的 $6$ 个节点二进制为 $110_2$，$1$ 的位置恰好指示了对应位置 $j$ 需要跳跃
4、实现上，初始化最上面虚拟的点 $fa[1][0] = 0$ (无意义)，操作上需要求 $fa[][]$ 数组，再求 $lca$。对于求数组，可以通过 DFS 得到，转移方程为 $fa[x][j] = fa[fa[x][j-1]][j-1]$，例如求 $fa[x][2] = fa[fa[x][1]][1]$ (求 $x$ 向上走 $2^2$ 步，等同于从 $x$ 向上走 $2^1$ 步再走 $2^1$ 步)，在 DFS 过程中，上面的点的 $fa[][]$ (即转移方程右侧)是已知的；此外，对于 $dep[]$ 有 $dep[x] = dep[fa[x][0]] + 1$ (深度为父节点 $+1$)。对于求 $lca$，给定两点 $x, y$，首先将深度大的(假设是 $x$)向上跳至二者在同一深度(用上面的方法跳跃)，判断 $x, y$ 是否相等(因为可能 $y$ 就是 $x$ 的祖先)，相等就输出 $y$；如果不相等，那么二者一起向上跳，依然从大到小枚举 $j$，但条件为若 $fa[x][j] = fa[y][j]$ 则不跳 (始终保持两个点不相等)，这样操作后，最终两个点会留在 $lca$ 的子节点，所以返回父节点 $fa[x][0]$ 即为 $lca$

01Trie

1、Trie 指字典树：简单地说，对于 $abcd, abcc, abca, acca$ 这四个字符串，互相之间有相同前缀，将它拆分成字符，建成边权为字符、点权为到该点为止相同前缀的字符串个数的树，称为 Trie 树，树的高度为字符串长度，如下图(蓝色为边权，红色为点权)。其通常处理前缀问题(如判断某个字符串作为前缀出现多少次)，但实际很少用到 Trie 树，常用的是 01Trie 树
2、01Trie 存储的不是字符，而是二进制的 $0, 1$，用于表示数字，基于二叉树：例如数组内有数字 $5 = 0101_2, 7 = 0111_2, 2 = 0010_2, 10 = 1010_2$，便可以用01Trie 树来存储表示这个数组，树的高度为最长二进制位数，如下图所示
3、01Trie初始只有一个空节点(初始节点 $0$)，采用动态开点的方式，其每个节点存储点权 $val$ 和两条边 $0, 1$ 分别指向的子节点 $son[0], son[1]$。更新时，没有的节点就动态开点，经过的节点点权 $+1$，对应二进制位为 $0$ 就左走，为 $1$ 就右走。对于数值范围在 $10^9$ 内的(约 $30$ 位二进制)，01Trie 通常需要 $32n = N \lt\lt 5$ 的空间

权值线段树

1、权值线段树：输入操作次数 $q$ ($q \leq 2 \times 10^5$)，起始你有一个空的多重集合(允许元素多次出现)，对于每次操作：输入 $1\ x$ 表示向集合添加元素 $x$，输入 $2\ l\ r$ 查询大小在 $[l, r]$ 之间的元素个数，输入 $3\ k$ 查询集合中第 $k$ 小的元素
2、先前介绍的线段树用于维护原数组的区间信息，而权值线段树用于维护数组元素的某种属性，例如元素出现次数或其他权值(但一般就是维护元素出现次数，即维护元素出现次数这个桶)，数据结构上与线段树类似
3、以维护元素出现次数为例，原数组若为 $\{1, 2, 1, 3, 5\}$ ，则元素出现次数的桶内为 $\{[1]:2,\ [2]:1,\ [3]:1,\ [4]:0,\ [5]:1\}$ 。给这个桶建立线段树即为权值线段树，每个节点的管辖区间表示管辖数字的范围，权值为管辖范围内这些数字的出现次数，如节点 $\{[1, 4] : 4\}$ 表示数字 $1 \to 4$ 共出现了 $4$ 次(下图为线段树结构，请按上述描述类比理解权值线段树的结构)，树的叶子结点从左至右对应这个桶本身且管辖区间(对应桶的下标，也即元素值)从左至右都是升序的
4、权值线段树可以进行的操作有单点更新(不依赖 $lazytag$，插入一个元素时更新线段树权值)、数量查询(查询整个数组中元素大小在 $[l, r]$ 之间的元素个数)、数值查询(查询整个数组中第 $k$ 大/小的元素值)，所有操作从根节点开始。单点更新，与线段树搜寻策略相同，但可以搜寻过程中直接更新权值(因为不需要维护 $lazytag$)，当然也可以找到叶子后递回时pushup。数量查询，即对桶求区间和，在权值线段树上的处理和加法线段树是相同的，凑出完整的询问区间求和即可
5、数值查询，查找第 $k$ 小的元素值，从根节点起，看左子节点权值 $t[l]$：由于管辖区间(对应桶的下标，也即元素值)从左至右都是升序的，权值 $t[l]$ 则表示前 $t[l]$ 小的元素都在左子节点区间。如果 $t[l] \geq k$，说明第 $k$ 小在左子节点区间，应向左继续查找第 $k$ 小；否则，则应向右查找第 $k - t[l]$ 小的元素(因为左区间有 $t[l]$ 个更小的元素，向右查询时应减去 $t[i]$ 排除掉这些元素)；最后，应查找到一个叶子结点，其管辖区间即为所求元素值。类似地，查找第 $k$ 大时应判断右子节点权值，如果 $t[r] \geq k$ 则向右查第 $k$ 大，否则向左查第 $k - t[r]$ 大

线段树

1、先前学习了运用树状数组维护区间和，而线段树是一种更高效更通用的方法，通过 $lazytag$ 优化后可以在 $O(\log n)$ 下完成区间修改和查询(朴素版只能单点修改和区间查询)，还可以维护更多的区间信息(区间和、区间积、异或和、最值等满足可加性或集合合并性质的信息)，运用了分治思想
2、线段树是一种基于二叉树的数据结构，朴素版的每个节点包含的信息有：编号 $o$、管辖区间 $[s, e]$、权值(即维护的区间信息)。为了实现区间修改，还会加入懒标记 $lazytag$