树上问题 #

LCA最近公共祖先与树上倍增 #

LG P4281 [AHOI2008] 紧急集合 / 聚会 #

给定一颗n节点无根树，然后有q次询问，每次询问给定三个点编号，给出树上一个节点到这三个节点的距离之和最小，同时求出最小值 $1 \leq n, q \leq 5 \times 10^5$

• 三个点有关LCA的结论：两两的LCA共三个，其中深度小的两个必重合，且恰为三者的LCA，题设距离和最小的节点就是三点中深度大的那个LCA

P1967 [NOIP 2013 提高组] 货车运输 #

给定一个 $n$ 顶点 $m$ 条边的带权无向图，给定 $q$ 次询问，每次询问给出两个不同编号顶点，查询这两点间路径的最小边权的最大值，若不存在路径输出 $-1$ $1 \leq n \leq 10^4, 1 \leq m \leq 5 \times 10^4, 1 \leq q \leq 3 \times 10^4$

• 一种方法是先建立最大生成森林，然后通过选择根节点使用树上倍增建立延根路径区间最小值结合LCA实现 $O(logn)$ 的查询
• 看题解还有多种做法，可以使用重构树等

SC11 听说你很会LCA？ #

给定一颗 $n$ 节点的有根树，给定 $q$ 次查询，每次询问给出区间 $[l, r]$，查询区间中节点的LCA $1 \leq n, q \leq 2 \times 10^5$

• 对于每个区间，我们可以建立两个倍增表，一个是单个节点的祖先的倍增表，一个类似st表的建立区间LCA的查询，这样可以实现 $O(1)$ 的单次查询，其中预处理使用 $O(1)$ LCA可以实现 $O(nlogn)$ 的预处理
• 另外事实上可以查询区间dfn的最大值和最小值，使用这两个节点的LCA即可获得区间LCA，只需使用st表即可做到 $O(nlogn + q)$

小白月赛 91G Bingbong的回文路径 #

给定一个 n 节点有根树，保证 1 是根，每个节点有一个字符，给定q次询问，每次给定两个节点编号，问这两点间简单路径的字符串是否回文 $1 \leq n, q \leq 10^5$

• 挺难写的树上倍增与LCA结合字符串哈希
• 不过存在相比哈希更高级和严谨的做法，SA + 重链分治，不会

树的重心 #

树的重心有如下三种定义，求出来的点是一样的

1. 以某个节点为根时，最大子树的节点数最少，那么这个节点是重心
2. 以某个节点为根时，每颗子树的节点数不超过总节点数的一半，那么这个节点是重心
3. 以某个节点为根时，所有节点都走向该节点的总边数最少，那么这个节点是重心

补充性质： 4. 一棵树最多有两个重心，如果有两个重心，那么两个重心一定相邻 5. 如果树上增加或者删除一个叶节点，转移后的重心最多移动一条边 6. 如果把两棵树连起来，那么新树的重心一定在原来两棵树重心的路径上 7. 树上的边权如果都为非负数，不管边权怎么分布，所有节点都走向重心的总距离和最小

• 使用前两种定义，可以很容易结合树型DP获得重心节点，可以重心常常有两个重心，这个模板并不是很好写且经常我们只需要知道一个重心就可

P2986 [USACO10MAR] Great Cow Gathering G #

给定一颗 $n$ 个节点的同时带非负边权点权的树，边权贡献距离，计算一个节点使得其到其他所有节点的距离乘其点权之和最小，输出这个最小值(即寻找到带点权边权的重心并计算该路径权值和) $1 \leq n \leq 10^5$

• 注意到正权的分布不改变重心的分布，不过这里存在 $0$ 权边可能使得满足路径权值最小的点变多，变成一个包含重心的集合，但我们找到重心同样能计算这个权值。
• 寻找重心可以使用重心的定义即可，用点权替代无权树的单节点 $1$ 权值。计算权值使用简单的树型DP即可
• 或者使用换根dp也是可以算的，这样不需要依赖重心任何结论

CF670 div2 C. Link Cut Centroids #

给定一颗 $n$ 个节点的树，我们可以进行一次修改操作，删除一条边同时加上一条边，需要保证结果仍然是一棵树，并且使得修改后重心只有一个。可以证明必然存在一种方案使得成立 $3 \leq n \leq 10^5$

• 利用重心性质 $5$ 即可

树的直径 #

树的直径是树上最远点对间的路径，其路径长度称为直径的长度

普通树可认为边权为 $1$ ，树的直径只与边权有关，计算树的直径长度可以使用两次dfs法和树型DP，其中获取一条直径上的端点信息只能使用两次dfs法，但是两次dfs法不能解决带负边权的树

LG P3304 [SDOI2013] 直径 #

给定一颗 $n$ 个节点的非负边权树，求树的所有直径的公共边的数量 $2 \leq n \leq 2 \times 10^5$

LG P2195 HXY造公园 #

给定一个 $n$ 个点 $m$ 条边的无向图，给定 $q$ 次询问或者修改，有以下两种形式，始终保证图无环，即保证图为森林的形式

1. 给定 $x$，查询 $x$ 所在树的直径
2. 给定 $x, y$， 若 $x, y$ 不在一棵树上则在两颗树上连接一条边合并为一棵树且使得新树直径最小，否则不进行操作

$0 \leq m < n \leq 3 \times 10^5, 1 \leq q \leq 3 \times 10^5$

• 使用并查集维护每个连通块的直径
• 当两颗树合并时，新树的直径想要最小，可以将两个树的中心相连，即直径中点相连，设原来的直径分别为 $d_1, d_2$，则新树直径取 $max(d_1, d_2, \lfloor \frac{d_1}{2} \rfloor + \lfloor \frac{d_2}{2} \rfloor + 1)$

P2491 [SDOI2011] 消防 #

给定一颗 $n$ 个节点的非负边权树，现在可以标记一条长度小于 $s$ 的路径，使得离这条路径最远的点的距离最小，求这个最小值 $1 \leq n \leq 3 \times 10^5$

• 首先这个路径一定在某一条直径上是最优的，同时维护直径上每个点的非直径子树上距离这个点的最大距离
• 于是我们可以在直径上用双指针维护每一个长度不超过 $s$ 的最长链，计算前缀部分，后缀部分和链上部分三部分最大值的最小值

P1099 [NOIP 2007 提高组] 树网的核 这是弱化版的同一个题目，证明相关可以参考该题题解

LG P3629 [APIO2010] 巡逻 #

给定一颗 $n$ 个节点的树，可以选择一个点作为起点，走遍整棵树上的所有点，且回到起点，同时可以在树上新建 $k$ 条边，但要求新建边必须通过，计算最短路程长度 $3 \leq n \leq 10^5, 1 \leq k \leq 2$

• 首先在不建新边的情况下，从任意节点出发的最短路径总是 $2n - 2$
• $k = 1$ 时可以连接一条直径的两个端点，$k = 2$ 有点复杂暂时没做这个题

树上差分 #

LG P3128 [USACO15DEC] Max Flow P #

给定一颗 $n$ 个节点的点权树，给定 $m$ 条路径的端点，计算每个节点位于多少给定路径上，返回其中最大值 $2 \leq n \leq 5 \times 10^4, 1 \leq m \leq 10^5$

• 点差分的模板题

LG P3258 [JLOI2014] 松鼠的新家 #

给定一颗 $n$ 个节点的点权树，给定一个 $n$ 元数组 $a_i$ 表示以次需要经过的节点，初始位于节点 $a_1$ 每次从 $a_i$ 走到 $a_{i + 1}$，每次经过一个节点会花费这个节点点权的代价，终点不计代价，问最终总代价之和 $2 \leq n \leq 3 \times 10^5$

• 树上点差分直接做即可，注意每次的目标节点不重复计算

LG P2680 [NOIP 2015 提高组] 运输计划 #

给定一颗 $n$ 个节点的正边权树，给定 $m$ 个运输计划，每个运输计划 $(a_i,b_i)$ 表示从 $a_i$ 节点去往 $b_i$ 节点，每个运输计划的代价是路径边权和，你可以选择一条边，将其边权变成 $0$，你的目的是让所有运输计划代价的最大值尽量小 $1 \leq n, m \leq 3 \times 10^5$

• 一个较困难的题目，可以使用树剖，也可以使用二分答案 + 树上边差分、
• 对于差分方案，我们二分答案，对于路径和大于 $mid$ 的计划进行边计数形式的差分，我们可以去寻找满足通过路径数等于个数的边权最大值，判断改变这条边能不能使得最大边权减少到 $mid$ 之下

树链剖分 #

树上启发式合并 #

LG U41492 树上数颜色 #

给定一棵 $n$ 个节点的有根树，每个节点有一种颜色 $c_i$，给定 $q$ 次查询，每次查询给定节点 $x$，询问以 $x$ 为根的子树有多少种颜色 $1 \leq n, q, c_i \leq 10^5$

• 树上启发式合并板子

LG P9233 [蓝桥杯 2023 省 A] 颜色平衡树 #

给定一棵 $n$ 个节点的有根树，每个节点有一种颜色 $c_i$，统计有多少棵子树的每种颜色的出现次数都相等 $1 \leq n, q, c_i \leq 10^5$

• 树上启发式合并，在板子的基础上再维护每个次数对应的颜色个数以及子树大小可以判断是否是颜色平衡树

ICPC2025 成都站 - L #

给定一棵 $n$ 个节点的有根树，每个节点有两个权值 $a_i, b_i$，我们认为权值为 $0$ 是赖子能和任意数字相等，在一棵子树上可以任意的交换 $a_i$ 的权值，计算每个子树在上述要求下能不能满足每个节点都有 $a_i = b_i$ $1 \leq n \leq 2 \times 10^5, 0 \leq a_i, b_i \leq n$

• 单独统计 $0$ 的个数，对于每种整数我们做桶计数的时候认为 $a_i$ 占 $1$，$b_i$ 占 $-1$，然后使用树上启发式合并维护这个桶以及桶中元素的绝对值之和与 $0$ 个数做比较即可判断

CFedu 2 E. Lomsat gelral #

给定一棵 $n$ 个节点的有根树，每个节点有一种颜色 $c_i$，对于一棵子树，我们认为出现颜色最多的为支配颜色(可以有多种)，计算每个子树所有支配颜色编号之和 $1 \leq n \leq 10^5, 1 \leq c_i \leq n$

• 在模板的基础上再维护颜色次数最大值以及每种次数对应颜色编号之和

CF130 div2 E. Blood Cousins #

给定给定一棵 $n$ 个节点的有根树，给定 $q$ 次查询，每次查询给定 $x, k$ 计算节点 $x$ 的所有 $k$ 级表亲节点的个数 $1 \leq n, q \leq 10^5$

• 首先表亲节点个数不容易计算，首先使用倍增转化为 $k$ 级祖先的 $k$ 级子孙节点个数
• 我们对查询离线，将查询分配给每个 $k$ 级祖先，接着将节点深度作为颜色做树上启发式合并，就可以计算每个子树各个深度的节点个数进行查询

CF151 div2 E. Blood Cousins Return #

给定给定一棵 $n$ 个节点的有根树，每个节点有一个名字字符串 $s_i$，给定 $q$ 次查询，每次查询给定 $x, k$ 计算节点 $x$ 的所有 $k$ 级子孙中不同名字的个数 $1 \leq n, q \leq 10^5$

• 在上一个题的基础上我们对不同的名字进行区分，可以使用map做计算，这个题不需要使用倍增寻找祖先

CF383 div1. D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths #

LG P3302 [SDOI2013] 森林 #

Kruskal重构树 #

LG P2245 星际导航 #

给定一个 $n$ 节点 $m$ 条边的带边权无向图，给定 $q$ 次查询，每次查询给定 $x, y$ 输出从 $x$ 到 $y$ 的路径中的最大边权的最小值 $1 \leq n, q \leq 10^5, 1 \leq m \leq 3 \times 10^5$

• 这是Kruskal重构树的模板题，通过加边加点的建有根树结合树上倍增树型DP等技巧查询边权受限的一些查询
• 注意由于这个题本身问题简单，我们可以朴素的使用Kruskal算法建立最小生成树接着用树上倍增查询路径最大边权

LG P9638 「yyOI R1」youyou 的军训 #

给定一个 $n$ 节点 $m$ 条边的带边权无向图，给定 $q$ 次操作，有以下三种形式

1. 输入 $x$，将边权小于等于 $x$ 的边断开，注意这个删除不保留，下一次操作 $1$ 时会复原，同时被删除的边能进行操作 $3$ 的修改
2. 输入 $x$，查询此时 $x$ 所在连通分量的节点数
3. 输入 $x, w$，将第 $x$ 条边边权修改为 $w$，我们保证边权总是没有相同的时刻且边权的大小次序不会被操作 $3$ 改变

$1 \leq n, m, q \leq 4 \times 10^5$

• 大小次序不变实质上保证了重构树的形态不变，只进行了边权改变
• 每次操作 $2$ 查询时在节点及其所有祖先上进行二分+查询 $k$ 级祖先可以 $O(log^2n)$ 的复杂度查询，但是注意到我们实质上可以倍增的往上进行即可，时间复杂度 $O(mlogm + n + qlogn)$

LG P4768 [NOI2018] 归程 #

给定一个 $n$ 节点 $m$ 条边的带边权无向图，这个边权同时由高度 $h$ 和路程 $w$ 组成，给定 $q$ 次查询，每次查询给出 $v, p$ 表示出发点和限制高度，可以从出发点出发在限制高度以上的边上乘车运行到任意节点，接着步行走到节点 $1$，计算从出发点 $v$ 到 $1$ 的最少步行路程，并且强制在线 $1 \leq n \leq 2 \times 10^5, 1 \leq m, q \leq 4 \times 10^5$

• 在边上进行限制条件下查询最短路，dijkstra算法+Kruskal重构树的结合，时间复杂度 $O((m + n)logm + qlogn)$

AGC 2. D - Stamp Rally #

给定一个 $n$ 节点 $m$ 条边的连通无向图，给定 $q$ 次询问，每次询问给定 $x, y, z$ 查询从 $x, y$ 节点出发恰经过 $z$ 个不同节点(同一个节点可多次经过但计数只算一次)，问经过的最大节点编号的最小值 $3 \leq n \leq 10^5, n - 1 \leq m \leq 10^5, 1 \leq q \leq 10^5$

• 比较明显的是将边连接的顶点编号最大值排序建立重构树，这样深度越小能到达的编号越大
• 使用总边数计算最大编号比较困难，使用二分答案，若已知最大编号，能到达的节点是好计数的
• 注意到起点有两个，注意需要判断两者能到达的集合是否重合，时间复杂度 $O(mlogm + nlogn + qlog^2n)$

CF809 div2 E. Qpwoeirut and Vertices #

给定一个 $n$ 节点 $m$ 条边的连通无向图，给定 $q$ 次询问，每次询问给定一个区间 $[l, r]$ 问至少需要边集合前缀多少条边使得区间中的顶点连通 $2 \leq n \leq 10^5, 2 \leq m, q \leq 2 \times 10^5$

• 按边集合的输入顺序建立重构树，我们只需要查询区间LCA即可获取到答案

CF643 div1 D. Graph and Queries #

给定一个 $n$ 节点 $m$ 条边的不保证连通的无向图，每个节点有初始点权 $a_i$，保证节点权值互不相同，给定 $q$ 次查询或操作，有以下两种形式

1. 输入 $v$，查询 $v$ 所在连通块的最大点权，并将该点点权修改为 $0$
2. 输入 $k$，删除第 $k$ 条边

$1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 3 \times 10^5, 1 \leq q \leq 5 \times 10^5$

• 删除边破坏连通性的处理是非常困难的，而且我们不希望破坏重构树结构，我们可以这样操作，我们离线后按被删除顺序给边倒序编号(未被删除编最小的编号)，按编号从小到大建立重构树，于是优先被删除的节点在深度最小处，每次查询我们可以快速倍增到此时的根节点
• 对付查询最大值和修改为 $0$ 我们可以获取叶子的dfn接着在其上建立线段树解决这个问题，时间复杂度 $O(mlogm + (n + q)logn)$

虚树 #

CF339 div1. D. Kingdom and its Cities #

给定一棵 $n$ 节点的有根树，$1$ 为根节点，给定 $q$ 次查询，每次查询给定 $k$ 个节点作为关键节点，现在要标记最少的非关键节点使得每两个关键节点之间的路径都至少有一个点被标记，查询最小值或返回不存在方案 $1 \leq n, q, \sum k \leq 10^5$

• 虚树上进行树上DP即可，维护当前子树的根处剩余未断开的关键节点(值域只能是0/1)，和子树代价

LG P4103 [HEOI2014] 大工程 #

给定一棵 $n$ 节点的有根树，$1$ 为根节点，给定 $q$ 次查询，每次查询给定 $k$ 个节点作为关键节点，查询这些节点之间的最大距离，最小距离和两两距离之和 $1 \leq n \leq 10^6, 1 \leq q \leq 5 \times 10^4, 1 \leq \sum k \leq 2n$

• 虚树上进行树上DP，维护的DP数组比较多

LG P2495 【模板】虚树 / [SDOI2011] 消耗战 #

给定一棵 $n$ 节点的有根带边权树，$1$ 为根节点，给定 $q$ 次查询，每次查询给定 $k$ 个节点作为关键节点，我们可以花费边权为代价删除一些边，询问至少花费多大的代价使得从根无法到达任何关键节点 $2 \leq n \leq 2.5 \times 10^5, 1 \leq q, \sum k \leq 5 \times 10^5$

• 虚树上进行树上DP，其中特殊的步骤是获取虚树上的边权，在这个题里是原树上的路径边权最小值，可以使用树上倍增查询

LG P3233 [HNOI2014] 世界树 #

CF625 div1 E. Treeland and Viruses #

LG P3320 [SDOI2015] 寻宝游戏 #

静态点分治 #