树链剖分练习笔记
一些毒瘤的出题人总喜欢把序列上的问题放到树上来加大难度。
所以对于大多数的树链剖分的题目，树剖只是一个工具，实际上考察的还是数据结构（主要是线段树）的基本功……
难度分为 easy、easy+、normal、normal+、hard、hard+ 六个档次。
P3384 【模板】轻重链剖分/树链剖分（easy）
- 模板题。
P2590 [ZJOI2008]树的统计（easy）
- 模板题。
P3178 [HAOI2015]树上操作（easy）
- 模板题。
- 可以 DFS 序做到
1\log 。
P2146 [NOI2015] 软件包管理器（easy）
- 已安装用
1 表示，未安装用0 表示。 - 安装
x 相当于查询x 到根的路径上0 的个数并把它们全部修改为1 。 - 卸载
x 相当于查询x 子树内1 的个数并把它们全部修改为0 。 - 注意不能安装已安装的或者卸载未安装的。
P2486 [SDOI2011]染色（easy）
- 线段树维护序列颜色段数的树上版本。
P7735 [NOI2021] 轻重边（easy+）
- 此题的关键是：将修改看成把路径上的点染新的颜色，将查询看成求路径上同色相邻点对数量。
- 之后的做法就跟上一道题很相似了。
P3979 遥远的国度（easy+）
- 套路题（或者也可以说成带换根操作的模板题？）。
- 树链剖分是可以支持换根的，换根后显然对路径没有影响，只会对子树有影响。
- 假设当前根为
rt ，子树的根节点为u ，分为三种情况来讨论： -
P5478 [BJOI2015]骑士的旅行（easy）
- 注意到
k\le 20 就能想到一个很暴力的做法。 - 每个点用一个 multiset 维护骑士，vector 维护前
k 大，合并的时候就用 STL 的 merge 函数。 - 此题教育我们要善用 STL，不然你的码量可能非常惊人……
P4219 [BJOI2014]大融合（easy+）
- 注意数据没有强制在线，所以我们可以知道最终树的形态。
- 一条边上的负载相当于它所连的两棵子树的 size 的乘积。
- 用并查集维护当前集合内的深度更浅的点当作根，操作相当于链加，求单点值。
- 树剖暴力
2\log 可过，但因为求的是单点值所以也可以 DFS 序做到1\log 。
P3313 [SDOI2014]旅行（easy）
- 显然需要对每一个宗教都开一棵线段树维护信息。
- 内存爆炸了？动态开点即可。
P5903 【模板】树上 k 级祖先（easy）
- 实际上就是重剖的树上倍增做法扔到了长剖上复杂度优化为了
O(n\log n)-O(1) 。 - 但是常数太大了，比普通的树上倍增快了一点点，比重剖还慢，似乎没有什么用处……
CF1009F Dominant Indices（normal）
- 长剖优化 DP 神仙题，考虑一棵树共用一个 DP 数组，每个点的信息以 DFN 为开头储存。
- 重儿子的信息父节点直接拿来用，轻儿子的信息暴力合并，最坏复杂度为
O(\sum len)=O(n) 。
P3899 [湖南集训]更为厉害（normal）
- 会了上一道题后这道题的做法就很显然了。
- 将每个点的 size 当成点权，长剖优化 DP，复杂度仍然是
O(n) 。 - 我记得以前这道题叫《谈笑风生》，现在怎么改成《更为厉害》了？
P5904 [POI2014]HOT-Hotels 加强版（normal）
- 长剖优化 DP。
- 先咕着……
SP6779 GSS7 - Can you answer these queries VII（easy）
- 线段树维护序列最大子段和的树上版本。
SP375 QTREE - Query on a tree / P4114 Qtree1（easy）
- 模板题。
SP913 QTREE2 - Query on a tree II（easy）
-
利用重链 DFN 连续的性质确定第
k 个点。 -
可以只用树上差分+倍增，但常数不如树剖。
P4116 Qtree3（easy）
- 这题能想到很多做法，目前我想到了 4 个
2\log 级别树剖做法：- 树剖 + 线段树维护区间黑点个数，二分黑点位置。
- 树剖 + 线段树维护黑点的 DFN 的最小值，白点设为 INF。
- 树剖 + 平衡树（可以用 set）维护 DFN。
- 树剖 + BIT 倍增维护 DFN。
QTREE4~7 先咕着……
P4281 [AHOI2008]紧急集合 / 聚会（easy）
- 显然 LCA 作为集合点是最优的。
P3038 [USACO11DEC]Grass Planting G / SP12005 GRASSPLA - Grass Planting（easy）
- 模板题。
- 可以 DFS 序做到
1\log 。
P3833 [SHOI2012]魔法树（easy）
- 模板题。
P4092 [HEOI2016/TJOI2016]树（easy）
- 打标记相当于子树取
\max 。
P4315 月下“毛景树”（easy）
- 模板题。
P4427 [BJOI2018]求和（easy）
- 看到
k\le 50 做法就很显然了，预处理出 DFN 序k 次方前缀和。 - 树上差分+倍增也可以，但常数不如树剖。
P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego（easy）
- 利用重链 DFN 连续的性质确定最后的位置。
- 树上差分+倍增常数太大被卡掉了。
P4069 [SDOI2016]游戏（easy）
- 注意修改是一个一次函数，李超线段树维护区间最小值即可。
P4211 [LNOI2014]LCA（easy+）
- 考虑
dep[i] 的意义是i 到根的点数，而lca(i,z) 必然是在z 到根的路径上。 - 如果每次只加一个点
u ，将u 到根的路径上的点权+1 ，查询z 到根的路径上的点权和即可。 - 注意数据没有强制在线，所以将询问离线下来按照右端点排序即可。
P5559 失昼城的守星使（easy+）
- 考虑与上一题类似的做法。
- 对于一个点
u 对某条链的贡献，设这条链的 LCA 为v ，u 与v 的 LCA 为w 。 -
- 将
u 到根的路径上的边打一个+1 累加标记，查询v 到根的路径和即为重合部分。 -
-
P4312 [COI2009] OTOCI（easy）
- 注意数据没有强制在线，所以离线得到树的结构即可。
P5558 心上秋（easy+）
- 别说树上路径 LIS 问题了，就连序列上区间 LIS 问题你要是会做了都能写篇论文了……
- 注意边权
\le 5 ，所以我们直接暴力，先考虑序列上怎么做？线段树维护 DP。 - 定义
dp[x][i][j] 表示x 的区间内起点为i 终点为j 的最长不下降子序列长度。 - 显然
dp[x][i][j] = \max\limits_{1\le k\le 5}\{ dp[ls(x)][i][k]+dp[rs(x)][k][j] \} 。 - 树上的话就是套一个树剖，当然本题由于是静态查询所以只用树上倍增也是可以的。
P3250 [HNOI2016] 网络（easy+）
- 如果没有第 2 种操作，线段树直接维护区间最大值即可。
- 所以我们把每个线段树节点都开一个堆来维护最大值。
- 时间复杂度
3\log ，空间复杂度2\log ，卡卡常优化一下就冲过去了。 - 可以整体二分做到时间复杂度
2\log 。
P2542 [AHOI2005] 航线规划（easy+）
- 注意数据没有强制在线，离线得到树的结构，时间倒序考虑加边。
- 修改很容易把人误导成 tarjan 缩点，然后想怎么快速实现动态缩点……
- 实际上询问的是两点间距离，那么我们把修改转化为将一条路径的边权都改为
0 不就可以了吗？
P6021 洪水（normal）
- DDP 模板题，但是有纯树剖做法，normal 给的是这个做法。
- 显然有 DP 柿子
dp[u]=\min\{ a[u],\sum\limits_{v\in son[u]} dp[v] \} ，不妨设s[u]=\sum\limits_{v\in son[u]} dp[v] 。 - 考虑对一个点
u 进行了单点修改会对它的哪些祖先x 的dp[x] 产生贡献。 - 首先
dp[u] 的变化量可以计算出来，设其为c ，则对s[fa] 的贡献也是c 。 - 如果
s[fa]+c\le a[fa] ，那么dp[fa]\leftarrow s[fa]+c ，同时dp[fa] 的变化量也可能对它的fa 产生贡献。 - 相当于将
u 到根的路径找到第一个点x 满足s[x]+c>a[x] ，并把u 到x 的路径上的点（不含x ）都+c 。 - 如果原来
s[x]<a[x] ，但是现在s[x]+c\ge a[x] ，那么dp[x]\leftarrow a[x] ，变化量为a[x]-s[x] ，继续重复上述过程。 - 如果原来
s[x]\ge a[x] ，那么dp[x] 没有发生变化，不会对它的祖先产生贡献，结束修改。 - 因此上述过程就是将
u 到根的路径上分成若干段，每段的dp 值都+c 。 - 找到每段的段顶
x 可以考虑将s[x]+c>a[x] 变形为c>a[x]-s[x] ，线段树维护区间a[x]-s[x] 的最大值即可。 - 同时也可以发现对
a[u] 和s[u] 的修改以及dp[u] 的查询都可以在这一棵线段树上进行。 - 但是问题在于时间复杂度上，每次修改后
u 到根的路径上的段数最大是O(n) 级别，如何保证时间复杂度？ - 注意到对
a[u] 的修改是将加上一个非负整数，也就是说s[u] 是非严格单调递增的。 - 所以除非对点
x 本身进行修改，只对x 子树内的点u 进行修改最多只会发生一次s[x]+c>a[x] 的转变。 - 因此均摊下来段顶
x 的次数不超过O(n+m) 次，均摊总时间复杂度为O((n+m)\log^2 n) 。 - 如果此题修改可能存在负数怎么办？纯树剖就没法做了只能 DDP 了……
P1600 [NOIP2016 提高组] 天天爱跑步（easy+）
- 此题有树上差分和线段树合并做法，但是这都是静态做法，我想到了一个很简单的树剖动态做法。
- 树剖变成序列上的问题，等价于插入一些线段，查询某个点
(x,y) 在多少条线段上。 - 需要注意的是这些线段的斜率只有
1 和-1 ，所以考虑将坐标轴旋转45\degree ，用线段树分别来维护。 - 于是就转化为了在
\sqrt{2n} 个时间点上，将某一个时间点的区间+1 ，求某一个时间点的单点值，树剖 + 动态开点线段树2\log 很轻松地过掉了。 - 因此这道题可以进一步加强：插入某条路径，删除某条路径，查询某个点在时间点
t 上有多少条路径，回到操作k 之前的历史版本。 - 树剖 + 可持久化线段树即可，仍然是
2\log 做法。
接下来还有一车题，没时间了，先咕着……
To be continued...