[ Heavy-Light Decomposition ] 樹鏈剖分模板+LCA

在某些狀況下，我們希望對樹上a點到b點的路徑進行修改或查詢的動作，而且這些動作用一般的樹壓平RMQ或是離線處理無法完成的，這個時候我們可以利用特殊的方法將樹拆成長鏈。
長鏈可以搭配良好的資料結構。只要找出樹上所有長鏈，每條長鏈套用線段樹、BIT、Sparse Table、BST、Heap，就能降低時間複雜度。

可以利用簡單的做法將dfs序切成許多長鏈:

1. 首先先設定其中一點為根，算出每個子樹有多少節點
2. 樹上每個節點各自連向最大的子樹，相連的部分會自然形成鏈

通常步驟二會進行一次dfs，每次朝著最大的子樹走，每個節點記錄其時間戳記及所在的鏈(通常是記鏈首)，這樣就可以將樹壓平的結果切成許多鏈，使得樹鏈剖分同時可以做到樹壓平的操作。

我們可以進行一個簡單的證明:

• 假設節點數為V，由根往任意葉節點走，一旦遇到新鏈，新鏈的子樹必小於等於原鏈子樹，剩下的節點數量不到一半，所以沿途最多遇到 logV 條鏈。

因為一條路徑藉由 LCA 拆成兩段，沿途最多遇到 2*logV 條鏈，所以在任意兩點a,b間最多只需要進行2*logV次的區間操作，若是套線段樹之類的結構可以做到$\ord{log^2V}$
這些操作都可以在求LCA的過程中完成:

	#include<vector>
	#define MAXN 100005
	typedef std::vector<int >::iterator VIT;
	int siz[MAXN],max_son[MAXN],pa[MAXN],dep[MAXN];
	/*節點大小、節點大小最大的孩子、父母節點、深度*/
	int link_top[MAXN],link[MAXN],cnt;
	/*每個點所在鏈的鏈頭、樹鏈剖分的DFS序、時間戳*/
	std::vector<int >G[MAXN];/*用vector存樹*/
	void find_max_son(int x){
	siz[x]=1;
	max_son[x]=-1;
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==pa[x])continue;
	pa[*i]=x;
	dep[*i]=dep[x]+1;
	find_max_son(*i);
	if(max_son[x]==-1||siz[*i]>siz[max_son[x]])max_son[x]=*i;
	siz[x]+=siz[*i];
	}
	}
	void build_link(int x,int top){
	link[x]=++cnt;/*記錄x點的時間戳*/
	link_top[x]=top;
	if(max_son[x]==-1)return;
	build_link(max_son[x],top);/*優先走訪最大孩子*/
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==max_son[x]||*i==pa[x])continue;
	build_link(*i,*i);
	}
	}
	inline int find_lca(int a,int b){
	/*求LCA，可以在過程中對區間進行處理*/
	int ta=link_top[a],tb=link_top[b];
	while(ta!=tb){
	if(dep[ta]<dep[tb]){
	std::swap(ta,tb);
	std::swap(a,b);
	}
	//這裡可以對a所在的鏈做區間處理
	//區間為(link[ta],link[a])
	ta=link_top[a=pa[ta]];
	}
	/*最後a,b會在同一條鏈，若a!=b還要在進行一次區間處理*/
	return dep[a]<dep[b]?a:b;
	}

view raw Heavy-Light Decomposition.cpp hosted with ❤ by GitHub

若樹鏈剖分的目的只是為了求LCA，build_link()及find_lca()有更好的做法:

	inline void build_link(int root,int n){
	pa[root]=-1;
	for(int i=1;i<=n;++i){/*假設節點編號是1~n*/
	if(~pa[i]&&max_son[pa[i]]==i)continue;
	for(int j=i;j!=-1;j=max_son[j])link_top[j]=i;
	}
	}
	inline int find_lca(int a,int b){
	while(link_top[a]!=link_top[b]){
	if(dep[link_top[a]]>dep[link_top[b]])a=pa[link_top[a]];
	else b=pa[link_top[b]];
	}
	return dep[a]<dep[b]?a:b;
	}

view raw Heavy-Light Decomposition LCA.cpp hosted with ❤ by GitHub

這就只需進行一次DFS