树链剖分
概念
重儿子： 一个结点的siz（子树大小）最大（相同则选任意）的儿子。其他的为轻儿子。
重链： 连向重儿子的边。其他的为轻链。
可以看出，所有轻链长度为1且连接两条重链。（非重儿子的叶子结点自身独自看作一个重链）
LCA
将两个点一步一步跳到一个重链上。一个深度大的点跳到这个点所在重链的top（深度dep最小），top再转到fa[top]；重复这个过程直到两个点的top相同（在一条重链上）。
再来分析以重链为集合的好处，以往需要用倍增法逐级上跳，而现在你会发现点的跳跃幅度变大，也就是说时间更优。
树转数组
遍历root，优先遍历重儿子，回溯后再遍历其他轻儿子，此时所得的dfs序记录为id。id[x]=y表示x点在所开数组（线段树）中的下标为y。这样就把树形结构变成了线性结构。
而显然，一个重链上的连续结点的id值连续，那么这个比较适合配合线段树。比方说我需要修改两个点之间的路径上的值，我可以把这条路径看成多条重链（或是一部分）。
对于每条重链上，我需要动的那部分id值连续，那么就是区间更新或查询了。
子树操作
除链外的另外一个强大的应用。例如修改一棵子树，那么我们知道，一棵子树的dfs序连续，若root的size为5，id为1，那么这棵子树的dfs序为：。
模板（配合线段树）
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register i=a;i<=b;i++)
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid (l+r>>1)
const int maxn= ,maxm= ;
// 权值存于点
int n,m;
int v[maxn];
int head[maxn],nex[maxm*2],to[maxm*2],now;
inline void add(int a,int b){
nex[++now]=head[a];head[a]=now;to[now]=b;
}
// 跑出的数组
int w[maxn];
// 跑出树的信息
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
void dfs_init(int p,int f,int deep){
fa[p]=f;
dep[p]=deep;
siz[p]=1;
int maxx=-1;
for(register int i=head[p];i;i=nex[i]){
int uv=to[i];
if(uv==fa)continue;
dfs_init(uv,p,deep+1);
siz[p]+=siz[uv];
if(siz[uv]>maxx){
maxx=siz[uv];
son[p]=uv;
}
}
}
// 跑出对应dfs序
int top[maxn],id[maxn];
int cnt;
void dfs(int p,int rt){
top[p]=rt;
id[p]=++cnt;
w[cnt]=v[p];
if(!son[p])return;
// 先跑重儿子
dfs(son[p],rt);
for(register i=head[p];i;i=nex[i]){
int uv=to[i];
if(uv==fa[p]||uv==son[p])continue;
dfs(uv,uv); // 不是重儿子开新链
}
}
// 查询修改树
// 查询同
void update_tree(int s,int t,int Val){
while(top[s]!=top[t]){
if(dep[top[s]]>dep[top[t]])swap(s,t);
update2(id[top[t]],id[t],Val);
t=fa[top[t]];
}
if(dep[s]>dep[t])swap(s,t);
update(1,1,n,id[s],id[t],Val);
}
// 修改一棵子树
// 查询同
void update_sontree(int rt,int Val){
update(1,1,n,id[rt],id[rt]+siz[rt]-1,Val);
}
void init(){
memset(head,0,sizeof head);
now=cnt=0;
memset(son,0,sizeof son);
memset(f,0,sizeof f);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
rep(i,1,n)scanf("%d",v+i);
rep(i,1,m){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
int rt=1;
dfs_init(rt,-1,1);
dfs(rt,rt);
build(1,1,n);
//...op
}
}
配合树状数组
原题： http://acm.hdu.edu.cn/showproblem.php?pid=3966
题意：
点权，有两种操作：两个点间路径上的点权加（减）一个数；求一个点的权。
解析：
这里虽然是区间更新，但是为单点求值，所以可以用树状数组代替线段树。对于开出的数组（dfs序为下标），我们区间加可以用差分来维护，记w[i]为开出数组a[i]-a[i-1]，区间更新只需要w[l]+=v,w[r+1]-=v;。而求一个点的值只需要用树状数组做一个前缀和即可。
从网上找的模板有个错误，在找跳哪个时不是判断
dep[s]>dep[t]而是判断dep[top[s]]>dep[top[t]]，错了好久。。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid (l+r>>1)
#define LL int
#define debug(i) printf("",i)
const int maxn=5e4+4 ,maxm=5e4+4;
int read(){ int ans=0; char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans; return ans;
}
// 权值存于点
int n,m;
int v[maxn];
int head[maxn],nex[maxm*2],to[maxm*2],now;
inline void add(int a,int b){
nex[++now]=head[a];head[a]=now;to[now]=b;
}
// 树状数组
LL tr[maxn];
LL w[maxn];
void update(int p,LL Val){
if(p==0)return;
while(p<=n){
tr[p]+=Val;
p+=p&(-p);
}
}
inline void update2(int l,int r,LL Val){
if(l==0)while(1){}
update(l,Val);
update(r+1,-Val);
}
LL query(int p){
LL ans=0;
while(p){
ans+=tr[p];
p-=p&(-p);
}
return ans;
}
void build(){
for(int i=n;i>=1;i--){
w[i]=w[i]-w[i-1];
update(i,w[i]);
}
}
// 跑出树的信息
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
void dfs_init(int p,int f,int deep){
fa[p]=f;
dep[p]=deep;
siz[p]=1;
int maxx=-1;
for(register int i=head[p];i;i=nex[i]){
int uv=to[i];
if(uv==f)continue;
dfs_init(uv,p,deep+1);
siz[p]+=siz[uv];
if(siz[uv]>maxx){
maxx=siz[uv];
son[p]=uv;
}
}
}
// 跑出对应dfs序
int top[maxn],id[maxn];
int cnt;
void dfs(int p,int rt){
top[p]=rt;
id[p]=++cnt;
w[cnt]=v[p];
if(!son[p])return;
// 先跑重儿子
dfs(son[p],rt);
for(register int i=head[p];i;i=nex[i]){
int uv=to[i];
if(uv==fa[p]||uv==son[p])continue;
dfs(uv,uv); // 不是重儿子开新链
}
}
// 查询修改树
// 查询同
void update_tree(int s,int t,LL Val){
while(top[s]!=top[t]){
if(dep[top[s]]>dep[top[t]])swap(s,t);
update2(id[top[t]],id[t],Val);
t=fa[top[t]];
}
if(dep[s]>dep[t])swap(s,t);
update2(id[s],id[t],Val);
}
LL query_tree(int p){
int Id=id[p];
return query(Id);
}
void init(){
rep(i,1,n){
head[i]=0,son[i]=0,tr[i]=0;
}
now=cnt=0;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
int p;scanf("%d",&p);
init();
rep(i,1,n)v[i]=read();
rep(i,1,m){
int a=read(),b=read();
add(a,b);
add(b,a);
}
int rt=1;
dfs_init(rt,0,1);
dfs(rt,rt);
build();
while(p--){
char x[2];scanf("%s",x);
if(x[0]=='I'){
int s=read(),t=read();LL v=read();
update_tree(s,t,v);
}
else if(x[0]=='D'){
int s=read(),t=read();LL v=read();
update_tree(s,t,-v);
}
else{
int p=read();
printf("%d\n",query_tree(p));
}
}
}
}
配合线段树（区间更新）
原题： http://poj.org/problem?id=3237
题意：
有一棵树，n个点，边权，有三种操作：
- 一条边的权变为v；
- 反转a到b路径上的所有边的权值；
- 求a到b路径上的所有边权的最大值。
解析：
首先把边权转化为点权，即维护好dep后，权值转移到两个点中dep大的点。（dep[root]=0）
对于一次操作，假设两个点在一条重链上，那么假设t的dep较大，那么维护的区间为；假设两个点不在一条重链上，那么维护的区间为（因为重链上是，加上一条轻链：）。
AC代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<limits.h>
using namespace std;
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid (l+r>>1)
const int maxn=1e4+4;
int n;
int v[maxn];//点权
int head[maxn],nex[maxn<<1],val[maxn<<1],to[maxn<<1],now;
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int pointid(int edge){
int p1=to[(edge<<1)-1];// 链式前向星存图
int p2=to[edge<<1];
int p=p1;
if(dep[p2]>dep[p1])p=p2;
return p;
}
inline void add(int a,int b,int v){
nex[++now]=head[a];head[a]=now;to[now]=b;val[now]=v;
}
//************************************************
int w[maxn];//线段树基础数组
int trmax[maxn<<2];//线段树
int trmin[maxn<<2];
int laz[maxn<<2];
void build(int rt,int l,int r){
if(l==r){trmax[rt]=w[l];trmin[rt]=w[l];return;}
build(lson,l,mid);
build(rson,mid+1,r);
trmax[rt]=max(trmax[lson],trmax[rson]);
trmin[rt]=min(trmin[lson],trmin[rson]);
}
void pushdown(int rt){
if(laz[rt]){
int tmp=trmax[lson];
trmax[lson]=-trmin[lson];
trmin[lson]=-tmp;
tmp=trmax[rson];
trmax[rson]=-trmin[rson];
trmin[rson]=-tmp;
laz[rt]=0;
laz[lson]^=1;
laz[rson]^=1;
}
}
void opposite(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R){
int tmp=trmax[rt];
trmax[rt]=-trmin[rt];
trmin[rt]=-tmp;
laz[rt]^=1;
return;
}
pushdown(rt);
if(L<=mid)opposite(lson,l,mid,L,R);
if(R>mid)opposite(rson,mid+1,r,L,R);
trmax[rt]=max(trmax[lson],trmax[rson]);
trmin[rt]=min(trmin[lson],trmin[rson]);
}
void update(int rt,int l,int r,int pos,int Val){
if(l==r&&l==pos){
trmax[rt]=trmin[rt]=Val;
return;
}
pushdown(rt);
if(pos<=mid)update(lson,l,mid,pos,Val);
else update(rson,mid+1,r,pos,Val);
trmax[rt]=max(trmax[lson],trmax[rson]);
trmin[rt]=min(trmin[lson],trmin[rson]);
}
int query(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R){
return trmax[rt];
}
pushdown(rt);
int ans=-2e9;
if(L<=mid)ans=max(ans,query(lson,l,mid,L,R));
if(R>mid)ans=max(ans,query(rson,mid+1,r,L,R));
return ans;
}
//************************************************
// 跑出树的信息
void dfs_init(int p,int f,int deep){
fa[p]=f;
dep[p]=deep;
siz[p]=1;
int maxx=-1;
for(register int i=head[p];i;i=nex[i]){
int uv=to[i];
if(uv==f)continue;
v[uv]=val[i];//边权转点权
dfs_init(uv,p,deep+1);
siz[p]+=siz[uv];
if(siz[uv]>maxx){
maxx=siz[uv];
son[p]=uv;
}
}
}
// 跑出对应dfs序
int top[maxn],id[maxn];
int cnt;
void dfs(int p,int rt){
top[p]=rt;
id[p]=++cnt;
w[cnt]=v[p];
if(!son[p])return;
// 先跑重儿子
dfs(son[p],rt);
for(register int i=head[p];i;i=nex[i]){
int uv=to[i];
if(uv==fa[p]||uv==son[p])continue;
dfs(uv,uv); // 不是重儿子开新链
}
}
//树操作转线段树操作
void Change(int edge,int v){
int p=pointid(edge);
update(1,1,n,id[p],v);
}
void Negate(int s,int t){
while(top[s]!=top[t]){
if(dep[top[s]]>dep[top[t]])swap(s,t);
opposite(1,1,n,id[top[t]],id[t]);
t=fa[top[t]];
}
if(s==t)return ;
if(dep[s]>dep[t])swap(s,t);
opposite(1,1,n,id[s]+1,id[t]);
}
int Query(int s,int t){
int ans=-2e9;
if(s==t)return ans;
while(top[s]!=top[t]){
if(dep[top[s]]>dep[top[t]])swap(s,t);
ans=max(ans,query(1,1,n,id[top[t]],id[t]));
t=fa[top[t]];
}
if(s==t)return ans;
if(dep[s]>dep[t])swap(s,t);
ans=max(ans,query(1,1,n,id[s]+1,id[t]));
return ans;
}
void init(){
memset(head,0,sizeof(head));
memset(son,0,sizeof son);
now=cnt=0;
memset(laz,0,sizeof laz);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
rep(i,1,n-1){
int a,b,v;scanf("%d%d%d",&a,&b,&v);
add(a,b,v);
add(b,a,v);
}
int rt=1;
v[rt]=0;
dfs_init(rt,-1,1);
dfs(rt,rt);
build(1,1,n);
char x[8];
while(1){
scanf("%s",x);
if(x[0]=='D')break;
int a,b;scanf("%d%d",&a,&b);
if(x[0]=='Q')printf("%d\n",Query(a,b));
if(x[0]=='C')Change(a,b);
if(x[0]=='N')Negate(a,b);
}
}
}
不敲线段树的区间更新都忘了，pushdown中应该更新儿子的tr和laz。