树链剖分
在树上求LCA，我们常用的方法如：倍增法，离线Tarjin，转欧拉序，以及树链剖分。
树剖与其他算法相比，时间复杂度相近，而优点是可以与线段树结合，支持修改。
原理：
树剖就是将一棵树，根据子节点个数剖分成轻、重链，轻、重儿子，轻、重边。
轻、重儿子：重儿子为该点子节点中，子树体积（size）最大的，其余的为轻儿子。对于每一节点，有且只有一个重儿子。
轻、重边：重边是由重儿子与父亲节点组成的边，轻边是由轻儿子与父亲节点组成的边。
轻、重链：重链是由连续的重边组成，其余的为轻边。
同时，我们需要维护每条重链的链头，而对于一个轻儿子，其链头为本身。
在开始求解LCA之前，我们需要两次搜索，来维护以下信息：
重儿子son[i] 层数dep[i] 大小sz[i] 父亲节点fa[i] 链头top[i]
并使用连接表完成对树的存储。
第一次搜索，我们需要维护出重儿子、层数、大小、及父亲节点
void dfs1(int x,int f)
{
sz[x]=1;
dep[x]=dep[f]+1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f) continue;
dfs1(y,x);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
第二次搜索，我们需要维护链头
void dfs2(int p,int tp)
{
top[p]=tp;
if(son[p]) dfs2(son[p],tp);
for(int i=head[p];i;i=nxt[i])
{
if(to[i]!=fa[p]&&to[i]!=son[p]) dfs2(to[i],to[i]);
}
}
这里有一个细节，我们先搜索重儿子，其原因我们会在之后的线段树中做解释。
最后，类似于倍增法，我们让两个查询点向上“跳”到其链头的父亲节点处。
这种做法的优点在于，如果该链长度巨大，我们可以直接沿着重边跳上去，节省时间。
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
线段树：
在我们第二次dfs中，我们可再维护出DFS序
DFS序：在进行DFS时递归每个节点的顺序，每个节点仅进入一次。
在此，区分一下欧拉序。
欧拉序：DFS时的路线，及每个节点可以多次进出。
例：
在该树中：
DFS序为：1 3 5 6 7 8 9 2 4
欧拉序为: 1 2 4 2 1 3 5 6 5 7 5 3 8 3 1 9
在上文中我们提到，要优先遍历重儿子，这样的好处是，在DFS序中，所有重链上的节点都是连续的。
于是，我们便可以用线段树对这些链进行修改。
例：运用树剖进行一条路径上的区间查和
在上文LCA函数中，我们每次会向上跳一条重链，此时，我们便可用DFS序和线段树进行区间的求和。
int query_s(int l,int r,int x,int y,int p)
{
int mid=(l+r)>>1;
if(x<=l&&y>=r) return s[p];
int ret=0;
if(x<=mid) ret+=query_s(l,mid,x,y,lson);
if(y>mid) ret+=query_s(mid+1,r,x,y,rson);
return ret;
}
int qs(int x,int y)
{
int ret=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret+=query_s(1,n,idx[top[x]],idx[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret+=query_s(1,n,idx[x],idx[y],1);
return ret;
}
例题：洛谷P2590 [ZJOI2008]树的统计
本题是一道裸的树剖，需要单点修改、区间求和、以及区间求最大值。
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 30010
#define lson p<<1
#define rson p<<1|1
int head[maxn],to[maxn<<1],nxt[maxn<<1];
int top[maxn],fa[maxn],son[maxn],dep[maxn],sz[maxn],idx[maxn];
int n;
int v[maxn];
int num=0,tot=0,cnt=0;
int s[maxn<<2],m[maxn<<2];
#define inf -100000000
#define MADE return
#define BY 0
#define JZW ;
void ct(int l,int r,int p)
{
int mid=(l+r)>>1;
printf("%d to %d m=%d s=%d
",l,r,m[p],s[p]);
if(l==r)return;
ct(l,mid,lson);
ct(mid+1,r,rson);
}
int query_m(int l,int r,int x,int y,int p)
{
int mid=(l+r)>>1;
if(x<=l&&y>=r)
return m[p];
int ret=inf;
if(x<=mid) ret=query_m(l,mid,x,y,lson);
if(y>mid) ret=max(ret,query_m(mid+1,r,x,y,rson));
return ret;
}
int query_s(int l,int r,int x,int y,int p)
{
int mid=(l+r)>>1;
if(x<=l&&y>=r) return s[p];
int ret=0;
if(x<=mid) ret+=query_s(l,mid,x,y,lson);
if(y>mid) ret+=query_s(mid+1,r,x,y,rson);
return ret;
}
void build(int l,int r,int p)
{
int mid=(l+r)>>1;
if(l==r)
{
s[p]=m[p]=v[l];
return;
}
build(l,mid,lson);
build(mid+1,r,rson);
}
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f)
{
fa[x]=f;
sz[x]=1;
dep[x]=dep[f]+1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f) continue;
dfs1(y,x);
sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
}
void dfs2(int p,int tp)
{
top[p]=tp;
idx[p]=++num;
if(son[p]) dfs2(son[p],tp);
for(int i=head[p];i;i=nxt[i])
{
int y=to[i];
if(y!=fa[p]&&y!=son[p])
dfs2(y,y);
}
}
void update(int l,int r,int x,int v,int p)
{
int mid=(l+r)>>1;
if(l==r)
{
m[p]=v;
s[p]=v;
return;
}
if(x<=mid) update(l,mid,x,v,lson);
else update(mid+1,r,x,v,rson);
m[p]=max(m[lson],m[rson]);
s[p]=s[lson]+s[rson];
}
int qs(int x,int y)
{
int ret=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret+=query_s(1,n,idx[top[x]],idx[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret+=query_s(1,n,idx[x],idx[y],1);
return ret;
}
int qm(int x,int y)
{
int ret=inf;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret=max(ret,query_m(1,n,idx[top[x]],idx[x],1));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret=max(ret,query_m(1,n,idx[x],idx[y],1));
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++)
{
int v;
scanf("%d",&v);
update(1,n,idx[i],v,1);
}
int q;
scanf("%d",&q);
int d=0;
while(q--)
{
char op[10];
scanf("%s",op);
if(op[0]=='C')
{
int x,y;
scanf("%d%d",&x,&y);
update(1,n,idx[x],y,1);
}
if(op[1]=='M')
{
int x,y;
scanf("%d%d",&x,&y);
if(d==1) printf("
");
printf("%d",qm(x,y));
d=1;
}
if(op[1]=='S')
{
int x,y;
scanf("%d%d",&x,&y);
if(d==1) printf("
");
printf("%d",qs(x,y));
d=1;
}
}
MADE BY JZW
}
注意：对于线段树的操作要输入对应的DFS序