### 树链剖分知识点详解
#### 一、树链剖分的相关概念
**剖分目的**：树链剖分的主要目的是为了有效地处理树结构中的路径查询和更新问题。通过将树分解为一系列的链（即重链），可以显著提高算法的效率。这样做的关键在于利用数据结构来维护每条链的信息，从而达到对树路径信息维护的目的，并且这种维护的复杂度仅为 O(logN)。
**剖分方法**：
- **盲目剖分**：一种简单的剖分方法，但通常不是最优选择。
- **随机剖分**：通过随机方式决定剖分方式，也不够高效。
- **启发式剖分**：基于一定的策略进行剖分，如重边和轻边的概念，这是最常用且高效的剖分方法。
**轻边和重边**：
- 定义：对于树中的每个节点 U，假设 V 是 U 的儿子节点中 size 值最大的节点，则 (U, V) 被称为重边；其余的边则称为轻边。
- 性质：对于任意轻边 (U, V)，有 size(V) ≤ size(U) / 2。这意味着从根节点到任意节点的路径上，最多包含 O(logN) 条轻边和 O(logN) 条重路径。
#### 二、树链剖分的实现
**重链剖分**：实现树链剖分主要通过两次深度优先搜索（DFS）完成。
1. **找重边**：通过一次 DFS 记录所有重边。
- 算法伪代码：
```plaintext
FIND-HEAVY_EDGE(x, father, depth)
1. father → fa[x], depth → dep[x]
2. 1 → size[x], 0 → maxsize, 0 → son[x], ...
3. while there exists a child of x not be visited
4. do FIND-HEAVY_EDGE(child, x, depth + 1)
5. size[x] += size[child]
6. if size[child] > maxsize
7. then size[child] → maxsize
8. child → son[x]
```
2. **连重边成重链**：从根节点出发，沿着重边向下构建重链。对于不在当前重链上的节点，均以该节点作为起点构建新的重链。
- 算法伪代码：
```plaintext
CONNECT-HEAVY_EDGE(x, ancestor)
1. ++label → tid[x], ancestor → top[x], ...
2. if son[x] ≠ 0
3. then CONNECT-HEAVY_EDGE(son[x], ancestor)
4. while there exists a child of x not be visited
5. do CONNECT-HEAVY_EDGE(child, child)
```
**示例图解**：
- 考虑一个简单的例子，如下图所示：
其中，节点编号为 1 到 9，数字代表 size 值，粗线表示重边。
**维护重链**：
- 在剖分完成后，每条重链被视为一个区间，可以通过合适的数据结构（例如线段树或平衡树）进行维护。
- 将所有重链连接起来形成一个整体，便于统一管理。
**修改操作**：
1. **单独修改一个点的权值**：直接在数据结构中根据新的编号进行修改即可。
2. **整体修改点 U 和点 V 之间的路径上的权值**：
- 如果 U 和 V 在同一条重链上，直接在数据结构中修改 tid[U] 至 tid[V] 之间的值。
- 如果 U 和 V 不在同一条重链上，则需要逐步将 U 和 V 向同一条重链靠近，具体步骤如下：
- 如果 fa[top[U]] 与 V 在同一条重链上，则修改 U 与 top[U] 之间的权值，然后让 U 跳至 fa[top[U]]，变成第一种情况。
- 如果 U 需要经过多条重链才能与 V 相遇，则不断重复上述过程，直至 U 和 V 处于同一重链。
- 如果 U 和 V 都需要向上移动才能相遇，则选择 dep[top[x]] 较大的点 x 进行移动，直至两者位于同一重链。
**修改操作伪代码**：
```plaintext
CHANGE(x, y, d)
1. while top[x] ≠ top[y]
2. do if dep[top[x]] < dep[top[y]]
3. then SWAP(x, y), SWAP(gx, gy)
4. CHANGE-IT(tid[top[x]], tid[x], d)
5. top[x] → x
6. if dep[x] > dep[y]
7. then SWAP(x, y), SWAP(gx, gy)
```
以上介绍了树链剖分的基本概念及其具体的实现方法，包括重边和轻边的定义、重链剖分的过程以及如何通过数据结构维护这些重链，最后给出了修改操作的具体实现方式。通过对树链剖分的理解与应用，可以有效提高解决树形结构问题的效率。
