树链剖分/重链剖分
什么是树链剖分/重链剖分我们可以弄一道例题来看看：
现在给定一棵 \(n（1 \le n \le 10^5）\) 节点的树，每个节点上有一个数值，现在你可以进行 $m ( 1 \le m \le 10^5) $ 次操作。格式如下：
[*]1 x z 表示将 \(x\) 到 \(y\) 最短路径上的节点值加上 \(z\) 。
[*]2 x y 表示树求 \(x\) 到 \(y\) 最短路径上的权值和。
[*]3 x y 将子树 \(x\) 下的每个节点的权值加上 \(y\) 。
[*]4 x 求子树 \(x\) 下每个节点的权值之和。
怎么写呢？当然，你需要前置知识线段树。接下来，且听我慢慢道来。
先从构造一个完美的剖分数组开始
我们知道，一棵树可以通过DFS构造成一个序列，其中对于任意一棵子树（包括根节点），我们把他的节点个数叫做 \(siz\) 。子树 \(x\) 的大小就是 \(siz_x\) 。那这对剖分有什么帮助呢？对于一棵树的DFS序举例如下：
1
/ \
2 3
/
4
\
5那么DFS后，序列如下：
1 2 4 5 3可以看到，子树 \(x\) 到 \(x+siz_x\) ，就是整个子树 \(x\) 。我们暂时叫这个数组为剖分数组 \(tag\)。但这样并不是最优的，有的的时候无法保证前面阐述的规律，这个时候怎么办呢？我们可以分析一下，在这棵树中，\(1\) 有两个孩子，分别是 \(2\) 和 \(3\) ，而且 \(2\) 的子树大小比 \(3\) 大，那么我们就规定 \(2\) 是 \(1\) 的 重孩子 。从 \(1\) 到 \(2\) 的这条边我们叫做重链。可以得知，对于任意一个非叶子节点，都有其独有的重孩子，我们就可以根据重孩子来构造DFS的先后，因为我们优先遍历一棵树的所有重孩子，所以所有重孩子一定是连在一起的，上面就是一个说明。那优先从重孩子开始还有什么好处呢？我们知道，如果从轻孩子开始遍历去构造这个数组，那么时间复杂度可能会达到 \(O(n)\)（见后文）。但是如果从重孩子开始的话，就不一样了，我们可以证明其时间复杂度可以来到 \(O(\log_2n)\) 的单次询问复杂度，证明如下：
对于节点 \(u\) ，其重孩子 \(v\) 必然是所有子节点中子树最大的那个，即为:
\
又因为重孩子的子树大小 \(\ge\) 其他所有子节点的子树大小，因此对于任意轻孩子 \(w\) 有：
\
又又因为所有节点子树个数+1等于其父亲节点的包含的节点个数（有点拗口），即为：
\
根据上面的第二,三条定理，解不等式方程，可以得到对于：
\[\sum_{轻孩子w}size(w) \le size(u)-size(v)-1\]
所以可以知道：如果某个轻孩子节点\(w\) 的子树大小大于 \(\frac{1}{2} size(u)\) , 则以上定理不成立，违背重孩子的定义，所以，必然有对于任意 \(w\)：
\
因此，从根节点到任意节点得到路径上，最多只有 \(O(\log n)\) 条轻边（因为每次碰到轻边子树大小随见到原来的 \(\frac{1}{2}\) ,所以至多 \(\log^2n\) 就会到达根节点）
而又因为重孩子是连续的一段区间，所以一次线段树修改就可以，再加上轻边修改是每次 \(O(\log n)\)，最多 \(\log n\) 条，所以是 \(O(\log n)\) 时间复杂度，证毕。
至此，我们的树链剖分的关键部分就已经完成。
Code如下：
void dfs1(int root, int fa) {
fath = fa;
siz = 1;
dep = dep + 1;
for(auto i : tree) {
if(i == fa) continue;
dfs1(i, root);
siz += siz;
if(siz > siz])
son = i;
}
}
void dfs2(int root, int tp) {
top = tp;
dfn = ++cnt;
rev = root;
if(!son) return;
dfs2(son, tp);
for(auto i : tree) {
if(i == fath || i == son) continue;
dfs2(i, i);
}
}其中 siz 是表示大小，top表示链头（见后文），dfn 表示对于 \(root\) 节点，在剖分数组里的位置。rev 是反的 dfn，cnt 全局计数器，son 记录重孩子编号，dep 表示深度。
利用链表的思想，完成perfect的查询/修改
我们已经知道，怎么分割一个有效的剖分数组。就是不会用，怎么办呢？
还是拿出一棵树：
1
/ \
2 5
/ \ \
3 7 6
\ /
4 8
/ \
910构造出来的序列如下(-表示重链，表示轻边）
1-2-3-4-9 10 7 5-6-8现在我们将 \(10\) 到 \(8\) 之间的，过程如下：
[*]先使所有重链的链头为深度最小的节点，比如 \(8,6,5\) 的链头都是 \(5\)，\(9,4,3,2,1\) 的链头都是 \(1\)
[*]令所有轻边的链头就是其本身
那么修改的时候，每次选择深度大的条跳跃，直到两者链头相同。那么此时只需要修改当前 \(\min{u,v}\) 到 \(\max{u,v}\) （询问/操作的两个端点）就可以了！。
到这里我们也可以知道了吧，按照轻边来的话时间复杂度是 \(O(n)\) 的哦。千万小心！
因为查询和修改代码雷同，就不详细撰述了。
Code For Luogu P3384
#include#define int long longusing namespace std;const int maxn = 1e5+100;int num,fath,top,son,dep,siz;int lay,tag1+siz-1,z); } else if(op==4){ cin>>x; cout
页:
[1]