前言
书上只讲了重链剖分，菜鸡也只会这一种，想看其他的是别想了。
点权树剖
要会树链剖分，首先你需要了解一些概念。我们把一个节点的所有儿子节点中子树节点数最大的称为重儿子，也就是size最大的子节点。size的定义我在讲换根DP时说过，因此不再赘述。对于每个节点的重儿子，我们用 (son[x]) 来记录它，父亲节点到重儿子的那条边称为重边，而连向其他儿子的边则称为轻边。
可以试着想象一下，或者手画一棵树，就会发现，许多重边连在一起，构成了一条链，这条边的顶端节点，我们用 (top[x]) 来记录，其中 (x) 是这条链上的任意一个节点，也就是说，对于同一条链上的节点，它们的top的值都是一样的。
还可以发现，每条链的顶点，隔着一条轻边，就到了另一条链的节点上，也就是说，我们只要记录每个节点的父节点，就可以让它们转移到另一条链上去。
我们可以想到，如果可以一次跳一条链，这样求LCA岂不比倍增要快得多？当两个点跳到一条链上的时候，深度更小的那个自然就是LCA了，而这需要的只是简单的预处理罢了。
但是还有问题，我们不能一直跳，而且我们一次只能跳一个点，选哪个好呢？
这时top数组就有用了，两个点的top值不相等，说明两个点肯定还没有跳到同一条链上，而我们只要在每次跳之前判断一下x节点在的这条链的顶点和y这条链的顶点那个深度更大，每次跳深度更大的那个就是了。
树链剖分的基本原理就是如此，通过将一条条重链剖分出来，以达到快速维护树上信息的目的。
你可能还有疑问，不就是求个LCA，怎么又可以维护树上信息了呢？
别急，先让我们看一道模板题：树的统计。
没有什么花里胡哨的东西，讲的很明白，就是要你维护树上的信息，然而数据规模之大，是普通的算法所承受不了的。这时候，树链剖分就会发挥它的奇效了。
首先看到这些操作，有没有觉得很熟悉？没错，这正是线段树里面的惯常操作，只是现在不要求你维护序列，而要求你维护一棵树，那我们是否可以把树上的信息转换到一段序列上呢？
当然可以，我们只要以dfs序来构造一个线段树就可以了。dfs序，简单点说，就是用dfs遍历整棵树时，节点出现的顺序，我们只要在进入递归时和回溯时分别记录一次就好了，放到树链剖分里就只要记录进入递归时的顺序即可。
还记得我们剖分出来的那些重链吗？我们只需要在每次对一个节点进行遍历时，优先遍历它的重儿子，这样这条链在dfs序中就是一段连续的序列，我们到时候就可以非常方便的在线段树上进行操作。
说说做法吧，首先我们要用一个seg数组代表所有节点在线段树中的编号，也就是序列的下标，同时还要用一个rev数组，相反的记录序列中的每个下标对应的是树中的哪个点，这样方便我们在建树时可以方便的将树上信息转移到线段树上。
接下来的就很简单了，操作以模板题为例，我们可以仿造上面求LCA的方法，让两个一次一次的跳，每次利用线段树来查询一条链上的信息，最终循环结束，两个点已经在同一条链上，那么这时我们只要再查询u点到v点的信息，就可以了涵盖两个点间路径上的所有节点。当然，记得先判断一下u和v两点的深度，小的下标更小，查询时放前面。
说了这么多，就来看看代码吧。
先是预处理的
void dfs1(int x,int fa)
{
father[x]=fa;
dep[x]=dep[fa]+1;
size[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==fa)continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
void dfs2(int x,int fa)
{
if(son[x])
{
seg[son[x]]=++cnt;
top[son[x]]=top[x];
rev[cnt]=son[x];
dfs2(son[x],x);
}
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(top[y])continue;
top[y]=y;//跳过一条轻边，这个点就是新重链的顶节点
seg[y]=++cnt;
rev[cnt]=y;
dfs2(y,x);
}
}
要预处理的信息有很多，在写的时候一定要仔细，不要写错或写漏，树链剖分码量一般都很大，写错一个小细节可能就要花费你大量的调试时间。
接下来是询问的代码
void ask(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
query(1,1,n,seg[top[x]],seg[x]);
x=father[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
query(1,1,n,seg[x],seg[y]);
}
为了方便，我的query函数没有返回值，用全局变量summ和maxn，放在query函数内，每次询问时一起更新。
建树部分
void build(int k,int l,int r)
{
if(l==r)
{
sum[k]=Max[k]=num[rev[l]];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
Max[k]=max(Max[k<<1],Max[k<<1|1]);
}
num记录的是每个点的点权。
线段树修改和查询的代码就不在此列出来了，有需要可以看我这道题的完整AC代码。
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=3e4+10,M=1e5+24000;
int n,q,num[N];
int top[N],rev[M],seg[M],size[N],son[N];
int dep[N],father[N],sum[M],Max[M];
int Next[N<<1],ver[N<<1],tot,head[N<<1];
int summ,maxn;
void add(int x,int y)
{
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}
inline void query(int k,int l,int r,int L,int R)
{
if(L>r||R<l)return;
if(L<=l&&r<=R)
{
summ+=sum[k];
maxn=max(maxn,Max[k]);
return;
}
int mid=l+r>>1;
if(L<=mid)query(k<<1,l,mid,L,R);
if(mid<R)query(k<<1|1,mid+1,r,L,R);
//sum[k]=sum[k<<1]+sum[k<<1|1];
//Max[k]=max(Max[k<<1],Max[k<<1|1]);
}
inline void change(int k,int l,int r,int v,int pos)
{
if(pos<l||pos>r)return;
if(l==r&&r==pos)
{
Max[k]=sum[k]=v;return;
}
int mid=l+r>>1;
if(pos<=mid)change(k<<1,l,mid,v,pos);
if(mid<pos)change(k<<1|1,mid+1,r,v,pos);
sum[k]=sum[k<<1]+sum[k<<1|1];
Max[k]=max(Max[k<<1],Max[k<<1|1]);
}
void build(int k,int l,int r)
{
if(l==r)
{
sum[k]=Max[k]=num[rev[l]];
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
Max[k]=max(Max[k<<1],Max[k<<1|1]);
}
void dfs1(int x,int fa)
{
size[x]=1;
dep[x]=dep[fa]+1;
father[x]=fa;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==fa)continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
void dfs2(int x,int fa)
{
if(son[x])
{
seg[son[x]]=++seg[0];
top[son[x]]=top[x];
rev[seg[0]]=son[x];
dfs2(son[x],x);
}
for(int i=head[x];i;i=Next[i])
{
int v=ver[i];
if(top[v])continue;
seg[v]=++seg[0];
top[v]=v;
rev[seg[0]]=v;
dfs2(v,x);
}
}
inline void ask(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(fx,fy),swap(x,y);
query(1,1,seg[0],seg[fx],seg[x]);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
query(1,1,seg[0],seg[x],seg[y]);
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int main()
{
n=read();
for(int i=1;i<n;++i)
{
int x,y;
x=read();y=read();
add(x,y);add(y,x);
}
for(int i=1;i<=n;++i)num[i]=read();
dfs1(1,0);
seg[0]=seg[1]=top[1]=rev[1]=1;
dfs2(1,0);
build(1,1,seg[0]);
//for(int i=1;i<=seg[0];i++)printf("%d
",Max[i]);
q=read();
while(q--)
{
char s[12];
scanf("%s",s+1);
int u,v;
u=read();v=read();
if(s[1]=='C')
{
change(1,1,seg[0],v,seg[u]);
}
else
{
summ=0;
maxn=-1e9;
ask(u,v);
if(s[2]=='M')
{
printf("%d
",maxn);
}
else printf("%d
",summ);
}
}
return 0;
}
总之，树链剖分就是这么简单了。这里还有一些树上操作，以及一些注意事项，都是我做题时遇到的，一一列下。
-
要知道一个节点在进行递归时，这棵子树上的所有节点在dfs序中都是连续的，也就是说在线段树中下标连续，因此如果要你一次修改以x为根的子树上的所有节点，只要把l和r定为 (seg[x]) 和 (seg[x]+size[x]-1) 即可。
-
最短路径和路径是一样的，树的边是无向的，总共就n-1条，从x点到y点只有一条路径，哪有什么最短路与次短路之分……
-
修改一条链上的信息和查询一条链上的信息方法是一样的，换个函数名而已，应该不会有人不会吧……
-
略……
关于树的操作太多了，每道题都不一样，记住一些惯常操作就行了，其他的靠你自己推也应该可以推出来。毕竟数据结构题还是考你代码实现能力，思维能力要求不会太高。
边权树剖
我也不知道为什么又要弄一个大标题，其实也没什么好讲的……
进入正题，树链剖分中有些题它并不给你点权，而是给你边权，其他的跟点权的题一样，没什么区别。
那么怎么把边权转点权呢？我们用的办法一般是让边权变成子节点的点权。没错，也就是说对于一条边 ((u,v)) ，假如u是v的父节点，我们就把这条边的边权当做v点的点权，反之亦然，也就是说，根节点无权。
这事其实很简单，只要在dfs1函数中的循环里加上这么一条语句num[y]=w[i]，一切就水到渠成了。
还有一个要修改的地方就是当两点跳到同一条链上时，循环外的语句变成这样query(1,1,n,seg[x]+1,seg[y])。
这其实也很容易想明白，因为x这个点是深度最小的那个点，而它的权是它的父节点连向它那条边的权，显然不在我们的路径内。毕竟假设我们查询时路径上的点有t个，那么自然也就只有t-1条边要查询/修改。
还有一点要注意的就是，如果题目要求你修改的是输入的第k条边，那么你就要记录下输入的点，并在查询时判断一下哪个节点是子节点，因为我们第k条边的边权转移到的是当中的两点中的子节点上，不能修改错误。判断两点深度大小就可以实现了。
练手题：Grass Planting G
最后给出一道码量极大的boss题：旅游