### NOIP 树链剖分知识点详解
#### 一、树链剖分的相关概念
**剖分目的**：树链剖分的主要目的是为了更高效地处理树状结构上的路径信息维护问题，例如路径上的权值更新或查询等操作。通过树链剖分，可以将这些操作的时间复杂度降低至对数级别。
**剖分方法**：
- **盲目剖分**：简单直接，但效率较低。
- **随机剖分**：通过随机选择的方式来进行剖分，虽然在某些情况下可能效率较高，但在最坏的情况下仍然可能退化到盲目剖分的效果。
- **启发式剖分**：基于树的特性来进行最优的剖分，是最常用的剖分方法之一。
在这些方法中，**启发式剖分**因其高效的性能而被广泛采用。
**轻边和重边**：
- 定义 **size(X)** 为以 X 为根的子树的节点个数。
- 令 V 为 U 的儿子节点中 size 值最大的节点，那么边 (U, V) 被称为 **重边**，树中除重边外的边被称为 **轻边**。
- **重边** 形成的路径称为 **重路径** 或 **重链**。
**轻重边路径剖分的性质**：
- 对于任意轻边 (U, V)，有 size(V) ≤ size(U) / 2。
- 从根到某一点的路径上，不超过 O(log N) 条轻边，不超过 O(log N) 条重路径。
#### 二、树链剖分的实现
**重链剖分**：这是一种常见的树链剖分方式，其过程包括两次深度优先搜索（DFS）：
1. **找重边**：通过一次 DFS，记录所有重边。
- 函数 `FIND-HEAVY_EDGE(x, father, depth)` 可用于查找重边。
- 在这个过程中，`father → fa[x], depth → dep[x]`。
- 遍历 x 的所有未访问过的子节点，并递归调用 `FIND-HEAVY_EDGE(child, x, depth + 1)`。
- 更新 `size[x] += size[child]`。
- 如果 `size[child] > maxsize`，则更新 `size[child] → maxsize, child → son[x]`。
2. **连重边成重链**：以根节点为起点，沿重边向下扩展，形成重链。
- 函数 `CONNECT-HEAVY_EDGE(x, ancestor)` 可用于连接重边成重链。
- `++label → tid[x], ancestor → top[x]`。
- 如果 `son[x] ≠ 0`，则递归调用 `CONNECT-HEAVY_EDGE(son[x], ancestor)`。
- 继续遍历 x 的所有未访问过的子节点，并调用 `CONNECT-HEAVY_EDGE(child, child)`。
**维护重链**：
- 完成剖分后，每条重链相当于一个区间，可以使用合适的数据结构进行维护。
- 所有的重链首尾相接，形成一个连续的整体，便于操作。
**修改操作**：
- **单独修改一个点的权值**：直接根据新的编号在数据结构中修改。
- **整体修改点 U 和点 V 之间的路径上的权值**：
- **I. 若 U 和 V 在同一条重链上**：直接修改区间 `[tid[U], tid[V]]`。
- **II. 若 U 和 V 不在同一重链上**：
- A. **若 fa[top[U]] 与 V 在同一条重链上**：修改 U 与 top[U] 间的权值，然后 U 跳至 `fa[top[U]]`。
- B. **若 U 向上经过若干条重链和轻边与 V 在同一条重链上**：不断修改当前 U 和 top[U] 间的权值，再将 U 跳至 `fa[top[U]]`，直到 U 与 V 在同一条重链。
- C. **若 U 和 V 都是向上经过若干条重链和轻边到达同一条重链**：每次选择 dep[top[x]] 较大的点 x 进行修改，直到 U 和 V 在同一条重链。
**查询操作**：
- 查询操作的逻辑与修改操作类似，只是使用数据结构的不同查询方法。
- 函数 `QUERY(x, y)` 可用于实现路径上的查询操作。
- 当 `top[x] ≠ top[y]` 时，重复执行类似修改操作的逻辑，直至 `top[x] = top[y]`。
- 使用数据结构的查询操作 `QUERY-IT(tid[top[x]], tid[x])` 进行具体的查询计算。
#### 三、例题
针对树链剖分的应用问题，可以通过具体的例题来进行实践练习。比如，题目可能涉及求解两个节点之间的路径最小值、最大值或者路径上的其他统计信息。
树链剖分是一种非常有效的算法技术，能够帮助我们在树形结构上快速高效地完成路径信息的维护操作。通过对相关概念的理解和实现细节的掌握，可以更好地应用于实际问题的解决之中。
