突然发现树链剖分应该不算算法？
树链剖分：树\to链，方法：DFS序（dfn）。
前置问题：
- 将树从x到y结点最短路径上所有节点的值都加上z、求树从x到y结点最短路径上所有节点的值之和，在线
很好做对吧，树上差分，复杂度极其优秀，n\log n - 将以x为根节点的子树内所有节点值都加上z、以x为根节点的子树内所有节点值之和，在线
众所周知（前置知识）一棵子树的DFS序连续，树状数组走你，n\log n，超小常数 - 1+2
树链剖分，n\log^2n
既然树链剖分这么有用那么我们就来学吧
众所周知一棵树的DFS序有很多种（但是切记都满足一棵子树的DFS序连续）
那我们能不能把这个DFS序变特殊一点呢？答案是true
名词规定：
- 重儿子：对每个非叶节点，重儿子代表最重的儿子节点数量最多的儿子
- 重链：重儿子们连起来的链
- 轻边：不被任何重链包含的边
好像没了其他教程有其他名词但是我好像没用，如果用了给我说一声
本来要证明下重链条数不超过\log n条，发现有点bug，于是 bz证了一个点用树链剖分的方法最多跳\log n次。
首先我们解释一下什么叫“在重链上跳”。
我们先一个DFS把重儿子找出来：
void dfs1(int p)
{
size[p] = 1;
for (Link *now = head[p]; now; now = now->next)
if (fa[p] != now->p)
{
fa[now->p] = p;
depth[now->p] = depth[p] + 1;
dfs1(now->p);
size[p] += size[now->p];
if (size[love[p]] < size[now->p])
love[p] = now->p;//love:重儿子编号
}
}
完了你们又要吐槽我用指针链表了
然后我们找重链。top标记每个点所在重链的深度最小的点。下面这个求法保证每条重链的DFS序连续，这很重要，等会说：
void dfs2(int p)
{
dfn[p] = ++dfn[0];
if (top[p] == 0)
top[p] = p;
if (love[p])
{//先访问重儿子从而使重链DFS序连续
top[love[p]] = top[p];
dfs2(love[p]);
}
for (Link *now = head[p]; now; now = now->next)
if (love[p] != now->p && fa[p] != now->p)
dfs2(now->p), maxdfn[p] = maxdfn[now->p];
}
这样前置工作就完成了。我们完成了两件事情：求出每个点所在重链，保证DFS序对每条重链连续。我们来看看有什么用。（点下面有个下划线代表这个点本身构成一条重链。虽然很多地方认为单独一个点不算重链但我觉得算啦）
这样的DFS序对重链连续，对子树连续，我们这样就可以同时处理前面提到的两种问题了。
我们按DFS序为每个点的新编号来维护信息即可。先来看链：将10-11这条链的每个点加一个数：
淡粉色代表重链上操作，淡紫色代表跳到重链深度最浅的点的父亲处。通过每次跳跃所在重链深度较大的点，最终一定能跳到一条链上。右边划出了区间的操作。代码实现如下：
while (top[x] != top[y])
{
if (depth[top[x]] < depth[top[y]])
swap(x, y);//想一想，如果这个条件不满足会怎么样
sth.add(dfn[top[x]], dfn[x], z);//淡粉色操作
x = fa[top[x]];//淡紫色操作
}
if (dfn[x] > dfn[y])
swap(x, y);
sth.add(dfn[x], dfn[y], z);//一条链上了 最后一个淡粉色操作
那么链上求和就很简单了对吧。
那么对一棵子树呢？简单极了
ta.add(dfn[x], dfn[x] + size[x] - 1, read);
哦对了我们来证明一下：一个点跳到根所在重链最多需要\log n次
- 我们先画一个点（
1）； - 我们发现跳跃次数就是这个点到一个地方所经轻边数量，于是我们向刚刚画的一个点连一条轻边，新的点记为
2； - 然后我们发现这条边并不是轻边，我们还要向
1连一条边，于是现在就有3个点了，这个点记为3； - 我们再向
2连一条轻边，这条边的另一个点记为4，然后为了满足轻边的性质，2号点需要另一个儿子，而3号点需要2个儿子，现在就有3+3+1=7个点了，我们把点安在最深的那一层并且有一条轻边的点上，她就需要跳2次到1号点； - 这样推下去，我们发现我们的“轻链”的编号是
1,2,4,...，为了让这条链是轻链，我们要保证1的另一个儿子3的子树大小要和2的相同，2的另一个儿子5的子树大小要和4的相同......最终我们发现这棵树的节点数量与层数的关系与满二叉树对应关系相同（当然这不一定是满二叉树，如图例），然后如果要跳的点在“轻链”最底端的话，她就要跳层数减1次
拓展一下，在3号点所在子树也这么构造，那个点就需要跳层数减去2次，这样我们发现一条链需要跳2\log n次
明天补个图
"吐槽"
其实洛咕的板子难度不在树链剖分，而在于区间加查，以及取模
为什么我这么说？因为我用的树状数组维护区间加查，明明过了区间加查的板子但是用到这道题就是错
~~所以说，你这不是自己zuo吗~~
#include <cstdio>
#include <cctype>
struct Read
{
//...
} read;
const int N = 1000000 + 10;
int n, m, mod, origin[N];
int dfn[N], size[N], love[N], fa[N], top[N], depth[N], adfn[N];
inline void _a(int &a, long long v) { a = ((a + v % mod) % mod + mod) % mod; }
struct SegTree
{
//...
} ta;
struct Link
{
//...
}...;
inline void connect(int u, int v)
{
//...
}
void dfs1(int p)
{
size[p] = 1;
for (Link *now = head[p]; now; now = now->next)
if (fa[p] != now->p)
{
fa[now->p] = p;
depth[now->p] = depth[p] + 1;
dfs1(now->p);
size[p] += size[now->p];
if (size[love[p]] < size[now->p])
love[p] = now->p;
}
}
void dfs2(int p)
{
dfn[p] = ++dfn[0];
adfn[dfn[p]] = p;//反dfn，我在建线段树的时候用了
if (top[p] == 0)
top[p] = p;
if (love[p])
{
top[love[p]] = top[p];
dfs2(love[p]);
}
for (Link *now = head[p]; now; now = now->next)
if (love[p] != now->p && fa[p] != now->p)
dfs2(now->p);
}
template <typename _Tp>
inline void swap(_Tp &__a, _Tp &__b) { /*...*/ }
int main(void)
{
int root_id;
n = read, m = read, root_id = read, mod = read;
for (int i = 1; i <= n; ++i)
origin[i] = read;
for (int i = 1; i != n; ++i)
{
int u = read, v = read;
connect(u, v), connect(v, u);
}
dfs1(root_id);
dfs2(root_id);
ta.build(1, 1, n);
while (m--)
{
int x, y, z, sum = 0;
switch ((int)read)
{
case 1:
x = read, y = read, z = read;
while (top[x] != top[y])
{
if (depth[top[x]] < depth[top[y]])
swap(x, y);
ta.add(dfn[top[x]], dfn[x], z);
x = fa[top[x]];
}
if (dfn[x] > dfn[y])
swap(x, y);
ta.add(dfn[x], dfn[y], z);
break;
case 2:
x = read, y = read;
while (top[x] != top[y])
{
if (depth[top[x]] < depth[top[y]])
swap(x, y);
_a(sum, ta.get(dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if (dfn[x] > dfn[y])
swap(x, y);
_a(sum, ta.get(dfn[x], dfn[y]));
printf("%d\n", sum);
break;
case 3:
x = read;
ta.add(dfn[x], dfn[x] + size[x] - 1, read);
break;
case 4:
x = read;
printf("%d\n", ta.get(dfn[x], dfn[x] + size[x] - 1));
break;
}
}
}
详细代码可以看这里（当然这意味着你要上60分w）
关于树链剖分的题，可以看分类里面的文章哦