本文共 837 字，大约阅读时间需要 2 分钟。
一棵树上有n个节点，每个节点都有一个权值w。我们的任务是对这棵树进行三种操作：更新节点权值、查询路径上的最大权值和路径权值和。针对这些操作，我们使用树链剖分将树转化为链状结构，并结合线段树进行高效维护。
首先，我们对树进行预处理，计算每个节点的深度与父节点关系。通过深度优先搜索，记录每个节点的深度$d[v]$和父节点$fa[v]$。树链剖分算法根据节点的子树大小，确定重链，并重新编号节点，使得树结构转换为链状。这样可以用线段树来维护这些线性数据。
树链剖分的关键在于网络编程中的插入操作和递归深度优先搜索。插入操作将节点依次连接到树的根节点。递归DFS遍历子树，记录下子树的大小。重链点被重新编号，便于后续操作。
经过树链剖分后，我们用线段树构建每个重链段的存储结构。线段树支持区间更新和查询操作。节点数超过3×10^4，我们初始化线段树，采用$4maxn$的空间尺寸，以确保线段树合理分配内存。
对于路径查询，拆分路径到不同重链段，分别查询相应区间的最大值或和，然后合并结果。最大值查询使用线段树的区间查询最大值功能；和查询同样使用线段树区间查询，但返回总和。
如需查询从u到v的路径最大权值，先比较顶端节点的深度，确保u和v在同一条路径上。拆分重链段进行查询，合并最终结果。
处理每条会话时，判断操作类型。更新操作直接调用线段树的更新函数；查询操作按最大值或和方式拆分路径，分别查询并合并结果。输出最终结果。
节点编号重新分配后，每个节点具有新的id和权值。线段树内存预留足够的空间，支持动态查询。路径处理时，确保查询节点在同一条路径上，避免跨越错误。
线段树的构建和查询操作均为$O(\log n)$，适用于大规模数据。预处理算法的正确性依赖于树的重链剖分。
通过树链剖分和线段树的结合，有效地降低了树路径查询的复杂度，为处理大规模动态树问题提供了高效解决方案。
转载地址：http://yndhz.baihongyu.com/