树链剖分

树链剖分常用轻重边剖分，用两次dfs实现（有时为了防止深度过大栈溢出，用bfs）

剖分过程要计算以下七个值：

1.father[x]:x在树中的父亲；

2.dep[x]:x在树中的深度；

3.size[x]:以x为根的子树大小；

4.son[x]:x的重儿子；

5.top[x]:x所在重路径的顶部节点；

6.seg[x]:x在线段树中的位置（下标）；

7.rev[x]:线段树中第x个位置对应的树中节点编号，即rev[seg[x]]=x;

第一遍dfs可以计算前四个值，剩下的由第二遍dfs计算；

void dfs1(int u,int f){
	int e,v;
	size[u]=1;
	father[u]=f;
	dep[u]=dep[f]+1;
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v!=f){
			dfs1(v,u);
			size[u]+=size[v];
			if(size[v]>size[son[u]]) son[u]=v;
		}
	}
}

void dfs2(int u,int f){
	int e,v;
	if(son[u]){
		seg[son[u]]=++seg[0];
		top[son[u]]=top[u];
		rev[seg[0]]=son[u];
		dfs2(son[u],u);
	}
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(!top[v]){
			seg[v]=++seg[0];
			top[v]=v;
			rev[seg[0]]=v;
			dfs2(v,u);
		}
	}
}

构建线段树：

void build(int k,int l,int r){
	//k:节点编号;l,r:左右区间 
	int mid=l+r>>1; 
	if(l==r){//找到叶子节点 
		Max[k]=sum[k]=num[rev[l]];
		return;
	}
	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]);
}//节点维护两个信息：该区间总合，最值   

查询（u，v）路径信息：

void ask(int x,int y){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]dep[y]) swap(x,y);
	query(1,1,seg[0],seg[x],seg[y]);//已经在一条重路径上 
}