[ Lowest Common Ancestor , LCA Euler Tour Technique ] 最近共同祖先樹壓平轉RMQ算法

想法就是把樹壓平，然後紀錄當前節點u的深度在dep[u]，紀錄時間戳記，進入的時候要紀錄一次，出來的時候也要記錄，把當前點u進入的時間戳紀錄在in[u]中，時間戳的大小為2*n，所以必須用兩倍的記憶體來維護。之後就轉成RMQ問題
查詢a,b兩點的LCA=dep[in[a]]到dep[in[b]]中，最小深度的時間戳經過的那個點

	#define MAXN 100000
	typedef vector<int >::iterator VIT;
	int dep[MAXN+5],in[MAXN+5];
	int vs[2*MAXN+5];
	int cnt;/*時間戳*/
	vector<int >G[MAXN+5];
	void dfs(int x,int pa){
	in[x]=++cnt;
	vs[cnt]=x;
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==pa)continue;
	dep[*i]=dep[x]+1;
	dfs(*i,x);
	vs[++cnt]=x;
	}
	}

view raw Euler Tour Technique.cpp hosted with ❤ by GitHub

查詢:

	inline int find_lca(int a,int b){
	if(in[a]>in[b])swap(a,b);
	return RMQ(in[a],in[b]);
	}

view raw query.cpp hosted with ❤ by GitHub

RMQ的部分就要自己維護了，使用線段樹效能會非常差，在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多