毛毛虫剖分
毛毛虫剖分
其实就是一种重链剖分的重标号方法。舍弃较为没用的部分，让它实现更加强大的功能！
学了这个其实可以更加彻底地理解重链剖分的本质。
- [NOI2021] 轻重边
小 W 有一棵 \(n\) 个结点的树，树上的每一条边可能是轻边或者重边。接下来你需要对树进行 \(m\) 次操作，在所有操作开始前，树上所有边都是轻边。操作有以下两种：
- 给定两个点 \(a\) 和 \(b\)，首先对于 \(a\) 到 \(b\) 路径上的所有点 \(x\)（包含 \(a\) 和 \(b\)），你要将与 \(x\) 相连的所有边变为轻边。然后再将 \(a\) 到 \(b\) 路径上包含的所有边变为重边。
- 给定两个点 \(a\) 和 \(b\)，你需要计算当前 \(a\) 到 \(b\) 的路径上一共包含多少条重边。
\(1\le n,m\le 10^5,1\le T\le 3\)。
我们考虑重链剖分的实质，它给我们提供了两条信息：
- 每一条重链上节点的编号都是连续的。
- 每棵子树内的 dfs 序都是成段的。
发现一般的重链剖分题目里我们都用不到第二条性质，这道题也是这样。考虑魔改出一种符合我们需要的数据结构，它要（尽可能）支持：
- 每一条重链上节点的编号都是连续的。
- 重链上每个节点的轻儿子编号都是连续的。
- 所有与重链节点相连的点编号都是连续的。
考虑这样一种重标号方式：
- 常规重剖，找出所有的重链，把以根节点为链首的重链加入队列。
- 取出队首，依次对该重链上的节点进行标号，然后对重链上每个节点的轻儿子进行连续地标号，将这些轻儿子加入队列。同时预处理出来两个数组：\(\rm mx\) 表示重链中该节点及以上的点所连点的最大值，\(\rm mn\) 表示重链中该节点及以下的点所连点的最小值。这个是可以顺序预处理的。不断重复以上过程。
不难发现这样可以达成我们的目的，只是有一个小问题：部分重链的链首和链上的节点编号不一定是连续的。不过这个不是问题，就一个节点，在修改和查询的时候特殊处理就行。具体看代码。https://loj.ac/s/1840921
这样的标号方式支持我们对所有轻儿子和重链分别进行不同的操作。严格强于普通的重链剖分。唯一的缺点就是因为链首标号不连续会徒增一些常数，导致这题 LOJ 上才能 0.998s 极限卡过去。不太会卡常，有无大佬教教。