两大DFS

树链剖分是一个比较简单易懂的算法，其两个基础操作为两次dfs，第一次dfs求出每个节点的父节点（\(f_{i}\)），深度（\(dep_{i}\)）,子树大小（\(size_{i}\)），重儿子（\(son_{i}\)）。其中，重儿子是其子节点中字数最大的，所以不难写出第一次dfs的代码：

void dfs1(ll u,ll fa){
	f[u]=fa;
	dep[u]=dep[fa]+1;
	siz[u]=1;
	for(int i=0;i<e[u].size();i++){
		ll v=e[u][i];
		if(v!=fa){
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v] > siz[son[u]] || son[u]==0){
				son[u]==v;
			}
		}
	} 
} 

第二次dfs，就要拆树成链了。以重儿子优先的顺序来dfs遍历一遍树，记下每个点的新编号（\(dfn_{i}\))，新编号所对应的旧编号（\(rk_{i}\))，以及每一条重链的链顶。

void dfs2(ll u,ll t){
	top[u]=t;dfn[u]=++num;rk[num]=u;
	if(son[u]){
		dfs2(son[u],t);
	}
	for(int i=0;i<e[u].size();i++){
		ll v=e[u][i];
		if(v!=son[u] && v!=f[u]){
			dfs2(v,v);
		}
	}
} 

拆树成链之后可以做些什么

显而易见，同一条重链中的节点的\(dfn\)编号是连续的，所以我们就把一棵树拆成了若干连续的区间。不难想到，可以用线段树来维护这些连续的区间。因此，树链剖分最简单的应用：对树上两节点间的最短路径路径上面的节点进行区间修改和查询，没错，这运用了倍增的思想

注意：倍增的时候应跳低的链顶，即深度更大的那个。

void work(ll x,ll y,ll z){
	while(top[x]!=top[y]){
		if(dep[top[x]] < dep[top[y]]){
			swap(x,y);
		}
		//update or query
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	//update or query
}

一些注意事项

我们是以\(dfn\)序来建树的，因此，建树过程中的叶子节点应赋予其所对应的原\(dfs\)序的值，即：

if(l==r){
		t[rt]=base[rk[l]];
        return;
	}

使用线段树操作时要把节点转换成\(dfn\)序下标

update(1,1,n,dfn[top[x]],dfn[x],z);

线段树别忘了return，否则会RE