树链剖分专题题目

P2590 树的统计 IN Lv.13 & P1505 旅游 IN Lv.13

因为一段时间没有写树剖了，所以找了两道模板题。还好之前写的树链剖分思想没有忘太多，写两道就差不多有那种感觉了。

注意 P1505 的一些细节问题：因为这个是边转点，在修改的时候记得有没有套 idx。

void Rchangeedge(int x, int w){ // C i w 操作
    segtr.changepoint(1, 1, n, idx[edgeto[x]], w);
    // 这里的 idx 不要忘！否则你就会像我一样只 AC test11！
}

P2486 [SDOI2011] 染色 IN Lv.14

这道题还是用树剖，只不过是可以转化为：

线段树节点表示将的所有颜色从左到右所连成的一个颜色链，它的左端点颜色、右端点颜色和颜色段个数。

我们可以将其变为一个 struct 存储：

1
2
3

struct QJ{
    int lcol, rcol, ans;
}; //一个区间。变量意义为左端点颜色、右端点颜色和颜色段数量。

然后合并区间是简单的（注意这里是有序合并区间）：

如果左区间的右端点和右区间的左端点的两种颜色相同，那么合并到一起之后的总颜色段个数就是左区间的和右区间的。否则就不减去。

QJ operator + (const QJ &a, const QJ &b){
    if(a.ans == 0) return b;
    else if(b.ans == 0) return a;
    QJ c;
    if(a.rcol == b.lcol) c.ans = a.ans + b.ans - 1;
    else c.ans = a.ans + b.ans;
    c.lcol = a.lcol, c.rcol = b.rcol;
    return c;
}

然后修改和查询就还是像原来一样，用线段树、套树剖板子即可。

这道题是最近唯一一道只测了一次样例交上去就一遍过的题，非常牛啊。

P4281 紧急集合/聚会 HD Lv.10

这道题据说本来是道紫，结果后面因为出现了纯 LCA 做法而被降绿。恶心。

那么这里用纯 LCA 做法：考虑到集合点一定是三个点的所有三个 LCA 中深度最大的那个点。因为可以证明，这个点一定是某两个点的 LCA，所以这两个点是不会浪费步数的。而第三个点的 LCA 则在这个 LCA 之上，那么也不会浪费步数。然后求路径就用 dep 之差就可以了。怪不得被降绿了，原来啊~

P4116 QTree3 IN Lv.12

这道题用了一个我从未想到过的方法：还是树链剖分这是可以想到的吧，然后对于每一个链开一个 set！！然后记录所有在这条链里面的黑点，然后询问就一条链一条链往上跳就可以了。可能是因为我不熟悉 STL 吧。

P3979 遥远的国度 IN Lv.14

这道题如果没有换根操作的话那么就是一道树链剖分板子题。而现在有了换根操作，那么该怎么办？可以先钦定为根，设为实时首都位置，然后分类讨论：

若就是，那么直接查询全局最小值即可。
若不是的祖先，分两种情况：
- 若是的儿子，那么显然，这种情况下的的子树状态不改变，直接求即可。
- 若既不是的儿子也不是的祖先，那么画个图也可以知道，这种情况下的的子树形态也不改变。设，那么和是在以为根的子树上的两侧的。你换个根不过就是把所在的那条链拽到上面去了，根本不影响的子树的形态。所以也是直接求即可。
若是的祖先。设为在这一条链上的儿子，那么答案就是整棵树排除以为根的子树之外的所有点的最小值。因为你把点往上一拽，就会发现以为根的子树的所有点全部都跑到上面去了。我们在第二个 DFS 的时候，是记录了每一个点进子树的 dfn 和出子树的 dfn 的。所以我们求最小值就只用求即可。

P3250 网络 IN Lv.14

这道题的方法就是：还是先树剖。

然后在每一个线段树节点里面开一个堆，维护当前区间的最大值和当前删除的所有值。因为要求不造成影响的最大值，所以可以转化一下思路：某两个服务器出现交互请求，就相当于是在这个路径之外给所有的节点的堆加上这个重要度。查询就好查了：直接单点查询即可。

这里介绍具体的方法：

出现交互请求，给这条路径之外的所有点 push 一个重要度，我们可以边跳链，边记录所有的区间。这种区间就是，每个区间都在一条重链上，并且把这些区间合并之后刚好就是的路径。于是要在这些区间之外修改，就可以首先排个序，然后在中把这些区间踢掉，只修改剩下的点。修改就是给这个区间所在的线段树节点的最大值堆 push 进这个重要度。于是复杂度就变为了。
出现结束请求。这种修改方式和 1. 的没啥区别，就是修改变为了给这个区间所在的线段树节点的当前删除的值的堆 push 进这个重要度。

特别注意：因为这里是大区间会影响小区间，小区间则不会影响大区间，那么这两种修改的时候只用在当前区间修改即可。相当于是标记永久化。不用 pushdown。
单点查询：还是在线段树里查。但是每到一个区间的时候都要把这个最大值 max 上，也就是一路都要 max 当前区间的最大值。而因为又删了某些点，所以当最大值堆和当前删除值堆堆顶的数相同的时候，就要都 pop 掉，直到不相等或是删除值堆变为 empty 状态为止。

另外，有一个玄学问题，就是这道题使用链式前向星的空间复杂度会变的非常的“低劣”，而换为 vector 就不会 MLE。目前不清楚原因。

P2680 运输计划 IN Lv.13

这道题可以转化为，设置其中一条边为所花费的时间。因为这道题求的是距离的最大值，并且删边后的最小值，求最大值的最小值那么就二分答案（似乎是经典思想）。

设所需最短时间为。那么我们把所有距离的路径全部抓出来（设共有条），所选的边一定是在这些路径的交。因为若不为交，那么就会遗漏的路径。那么，很容易就想到枚举所有的边，如果被经过了次（也就是所有的路径都经过了它），这时如果路径最大值减去这条边小于，那么就说明这个答案可行，直接返回。否则返回。

计算一条边被经过的次数可以用树上差分解决。其中一种方法是给 LCA 节点的值，然后节点的值各加上。然后从下往上统计即可。

CF916E Jamie and Tree IN Lv.14

这道题疑似卡树剖跳祖先哈。

因为洛谷没有翻译，所以这里讲一下题目大意：

给定一颗个点的树，树上有初始点权。初始树根为。有个操作，你要实现：

1 v 将树根换成。
2 u v x 将以为根的子树的所有点权加上。
3 v 查询以为根的子树的点权和。

其中，初始点权和 2 操作的均。

这道题类似的换根修改上面好像讲过。所以接着上面的讲。

查询就是那道题的操作，对和分类讨论。修改同理。而现在要实现的就是换根找两点 LCA。

还是用分类讨论（据说这种一般都分类讨论）：

若均在的子树内，那么以为根的话子树形态不变。所以这种情况下答案就是原本的。
若一个在子树内，一个不在，那么换根后的 LCA 就是。
若均不在子树内，那么记。画图可以知道，若这两个不相等，答案就是和里面深度更大的那个。否则答案就是原本的。

做完之后，交上去，发现 TLE on test #12。排查了半个小时，发现是 CF 他卡我树剖跳祖先。这里把它换成倍增跳就过了。

P7735 [NOI2021] 轻重边 IN Lv.16

（因为昨天晚上 Phigros 定数更新了，这玩意就也跟着更新吧。但是15.16 → 15.18，没啥玩意）

这道题因为是树上路径修改和路径查询，所以可以用树链剖分做。

这个轻重边的转化不好想。可以这么转化：

将每一个点附上一个权值。当时，边为重边。否则为轻边。然后区间线段树维护即可。表示区间的方法还是像这道题一样，左端点颜色、右端点颜色和重边条数。

初始时可以在 build 的时候给每一个点赋上不同的点权。（这是推荐的做法。不推荐的做法就是像我一样给所有点点权赋为然后搞一堆特判）

P4216 [SCOI2015] 情报传递 IN Lv.15

这个风险控制值比较难维护，我们考虑转化一下。

因为每一个人的危险值是在他开始搜集情报那一天开始（值为），过一天增加的，所以可以考虑将其转化为开始搜集情报的时间。那么假设某个情报传递任务在第天进行，它的风险控制值为，那么就求这个路径上所有的点的总数即可。

因为我们要求区间的小于某一个数的值，所以可以使用可持久化权值线段树（主席树）维护即可。

具体地，先树剖，然后处理每一个人开始搜索情报的时间（若没有则为），很明显这个操作要离线。然后将它们插入主席树里。最后在路径上，边跳链边 query 即可。

P6098 Cow Land G IN Lv.13

嗯……(lll￢ω￢)不做评价。

SP6779 GSS7 Can you answer these queries-7 IN Lv.16

这道题还是典型的区间合并 + 树链剖分问题。但是这里有一个小细节：

因为每一个点的权值可以为负，所以在设 Lazytag 的时候一定要把初始值设为极大值或是极小值。要不然你会死掉。

JOI2012T5 JOI 国のお祭りの事情 IN Lv.15

这道题要让我们求出路径的距离有标记的点的长度的最小值，那么肯定就要求路径上的每一个点距离有标记的点的长度的最小值了。

那么就可以首先预处理出所有点到有标记的点的最小距离。这个多源点 Dijkstra 再取最小值不好弄，就可以将超级源点向所有有标记的点连一条有向边，然后从超级源点跑一遍单源 Dijkstra 就可以了。

现在求出了所有的点到有标记的点的值。及其为。那么我们就要求一条从的路径使最大。那么我们就可以建一条最大生成树。因为一条路径必定有边，所以可以设边的权值为来求最大生成树。这样就可以保证整条路径取的不漏。之后你走路径从到也就只会从这棵生成树上走了。（注：建最大生成树的方法和最小生成树相同。）

所以最终答案就是最大生成树上链的值了。可以使用树链剖分 + 线段树处理。