NOIP树链剖分习题讲解报告

P2590 [ZJOI2008]树的统计 P3384 【模板】轻重链剖分/树链剖分 P3950 部落冲突 P4092 [HEOI2016/TJOI2016]树 P2146 [NOI2015] 软件包管理器 ### NOIP树链剖分习题讲解报告 #### P2590 [ZJOI2008]树的统计 **题目概述：** 本题给出了一棵树，包含`n`个节点，每个节点有一个权值`w`。任务是对这棵树进行一系列的操作，并根据这些操作回答一些查询问题。具体的操作包括： 1. **CHANGE u t**：更改节点`u`的权值为`t`。 2. **QMAX u v**：查询从节点`u`到节点`v`路径上的最大权值。 3. **QSUM u v**：查询从节点`u`到节点`v`路径上的权值总和。 **输入格式：** - 第一行包含整数`n`，表示节点数量。 - 接下来的`n-1`行，每行包含两个整数`a`和`b`，表示节点`a`与节点`b`之间存在一条边。 - 第`n+1`行包含`n`个整数，第`i`个整数表示节点`i`的权值`wi`。 - 第`n+2`行包含整数`q`，表示操作总数。 - 接下来`q`行，每行包含一个操作。 **输出格式：** - 对于每个`QMAX`或`QSUM`的操作，输出一行表示该操作的结果。 **数据范围：** - `1 ≤ n ≤ 3 × 10^4` - `0 ≤ q ≤ 2 × 10^5` - 每个节点的权值`w`在`-3 × 10^4`到`3 × 10^4`之间。 **解题思路：** 为了高效地处理这类问题，可以采用**树链剖分**的技术。树链剖分是一种数据结构技术，它能够有效地处理树上的动态查询问题。树链剖分的核心思想是将树拆分成多个链，这样就可以通过线段树等数据结构快速查询链上的信息。具体步骤如下： 1. **预处理：** 进行DFS遍历树，计算每个节点的深度以及每个节点的重儿子（即连接节点与其重儿子之间的边是最长的）。 2. **构建树链：** 根据重儿子关系构建树链，使得树链尽可能长。 3. **构建数据结构：** 使用线段树或者其他合适的数据结构存储每个链的信息，便于快速更新和查询。 **实现细节：** - 使用邻接表表示树结构。 - 通过递归遍历计算节点深度、子树大小以及确定重儿子。 - 建立线段树或其他数据结构以支持高效查询和更新。 #### P3384 【模板】轻重链剖分/树链剖分 **题目概述：** 此题提供了一棵包含`N`个节点的树，每个节点有一个初始值。需要支持以下四种操作： 1. **1 x y z**：将从节点`x`到节点`y`最短路径上的所有节点值加`z`。 2. **2 x y**：求从节点`x`到节点`y`最短路径上所有节点的值之和。 3. **3 x z**：将以节点`x`为根节点的子树内所有节点值加`z`。 4. **4 x**：求以节点`x`为根节点的子树内所有节点值之和。 **输入格式：** - 第一行包含四个整数`N`, `M`, `R`, `P`，分别表示节点数量、操作数量、根节点编号以及所有输出结果的取模数。 - 第二行包含`N`个非负整数，表示每个节点的初始值。 - 接下来的`N-1`行，每行包含两个整数`x`和`y`，表示节点`x`与节点`y`之间有一条边。 - 最后`M`行，每行包含若干个正整数，表示一个操作。 **输出格式：** - 输出包含若干行，分别表示每个操作2或操作4的结果（对`P`取模）。 **数据范围：** - 对于30%的数据：`1 ≤ N ≤ 10`，`1 ≤ M ≤ 10`； - 对于70%的数据：`1 ≤ N ≤ 10^3`，`1 ≤ M ≤ 10^3`； - 对于100%的数据：`1 ≤ N ≤ 10^5`，`1 ≤ M ≤ 10^5`，`1 ≤ R ≤ N`，`1 ≤ P ≤ 2^31 - 1`。 **解题思路：** 此题同样是关于树链剖分的应用，但涉及的操作更为复杂。除了基本的树链剖分外，还需要额外考虑如何高效地更新节点值以及求解子树的和。具体的解决方案包括： 1. **预处理阶段：** - 计算每个节点的深度、子树大小。 - 构建树链，标记每个节点所在的链。 - 构建线段树或区间树，以支持高效的区间加法和区间求和。 2. **操作处理：** - 对于操作1和操作3，可以通过修改线段树中的值来实现。 - 对于操作2和操作4，可以通过线段树查询得到。 **实现细节：** - 使用邻接表表示树结构。 - 使用递归函数来计算节点的深度、子树大小及确定重儿子。 - 构建线段树或其他数据结构以支持区间加法和区间求和操作。 - 通过线段树更新或查询来处理题目中的各种操作。