[ link-cut tree ] 動態樹教學+模板

因為code太多容易顯示不出來，這裡有Gist連結
動態樹，一種支持斷邊、連邊的資料結構（要保證是樹或森林），可以維護路徑、但不能維護子樹。
類似於樹鏈剖分（建議先學完樹鏈剖分，再學LCT）。
只不過樹鏈剖分的輕重邊是根據子樹大小而決定的，這棵樹只能是靜態的。
而LCT中的“輕重邊”是根據最後一次操作決定的，最後一次處理了x這個點，那麼從x到根的路徑就是重鏈（每個父親只與一個兒子的連邊為重邊）。
用splay來維護每一條重鏈，以點的深度為關鍵字，即splay中的每個點左兒子深度都比他小，右兒子的深度都比他大（若只有一個點，那麼這個點單獨是一棵splay）。
如果還不知道splay tree的可以參考這裡

splay tree及其節點的一些函數:

	#include<vector>
	struct splay_tree{
	int ch[2],pa;/*子節點跟父母*/
	bool rev;/*反轉的懶惰標記*/
	splay_tree():pa(0),rev(0){ch[0]=ch[1]=0;}
	};
	std::vector<splay_tree> node;
	/*
	有的時候用vector會TLE，要注意
	這邊以node[0]作為null節點
	*/
	inline bool isroot(int x){/*判斷是否為這棵splay tree的根*/
	return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x;
	}
	inline void down(int x){/*懶惰標記下推*/
	if(node[x].rev){
	if(node[x].ch[0])node[node[x].ch[0]].rev^=1;
	if(node[x].ch[1])node[node[x].ch[1]].rev^=1;
	std::swap(node[x].ch[0],node[x].ch[1]);
	node[x].rev^=1;
	}
	}
	void push_down(int x){/*將所有祖先的懶惰標記下推*/
	if(!isroot(x))push_down(node[x].pa);
	down(x);
	}
	inline void up(int x){}/*將子節點的資訊向上更新*/
	inline void rotate(int x){/*旋轉，會自行判斷轉的方向*/
	int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x);
	node[x].pa=z;
	if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x;
	node[y].ch[d]=node[x].ch[d^1];
	node[node[y].ch[d]].pa=y;
	node[y].pa=x,node[x].ch[d^1]=y;
	up(y);
	up(x);
	}
	inline void splay(int x){/*將節點x伸展到所在splay tree的根*/
	push_down(x);
	while(!isroot(x)){
	int y=node[x].pa;
	if(!isroot(y)){
	int z=node[y].pa;
	if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(x);
	else rotate(y);
	}
	rotate(x);
	}
	}

view raw lct_splay_tree.cpp hosted with ❤ by GitHub

定義：

1. Preferred child：
   如果一個點是他父親結點的所有兒子中最後被訪問的，那麼他是他父親的Preferred child。
   每個點最多有一個Preferred child。如果x結點是最後被訪問的點，那麼他沒有Preferred child。
2. Preferred edge:
   每個點到自己的Preferred child的邊叫Preferred edge（相當於樹鏈剖分中的重邊）
3. Preferred path:
   由Preferred edge組成的鏈叫Preferred path（相當於樹鏈剖分的重鏈）

簡單來說就是一個節點在重鏈上的直接兒子定義為preferred child，連向該兒子的邊定義為preferred edge。

access(x):
我們用操作access(x)來表示訪問節點x為LCT的最基礎操作，使x到根結點的路徑成為重鏈。

如上圖，粗邊為重邊。

首先把x旋到他所在的splay的根部。
因為當前的x點是最後一個被訪問的點，所以他沒有Preferred child，因此要把右兒子與他斷開，右兒子成為新的一條鏈。
x的父親是y，把y旋到他所在splay的根結點，把此時y的右兒子與他斷開，把x連過來即可，相當於合併y和x所在的splay。
然後，再找y的父親，合併y與y的父親所在的splay，一直到根結束。
最終，x到根結點的路徑成為新的Preferred edge，而曾經的Preferred child都被拋棄。

	inline int access(int x){
	int last=0;
	while(x){
	splay(x);
	node[x].ch[1]=last;
	up(x);
	last=x;
	x=node[x].pa;
	}
	return last;/*回傳access後splay tree的根*/
	}

view raw lct_access.cpp hosted with ❤ by GitHub

有了access操作後，其他的操作就更容易實現了

make_root(x):
將x設為其所在的樹的根
首先access(x)，這樣x與根結點處在同一棵splay中。
設a=access(x)，而a是splay tree的根，因為要讓x成為整棵樹的根，所以x的深度要最小，我們只要在a上加一個區間反轉的標記rev就可以完成。
這裡提供兩種方式，最後都會把節點x轉到splay tree根的位置(這很重要)
1.

	inline void make_root(int x){
	access(x),splay(x);
	node[x].rev^=1;
	}

view raw lct_make_root1.cpp hosted with ❤ by GitHub

2.

	inline void make_root(int x){
	node[access(x)].rev^=1;
	splay(x);
	}

view raw lct_make_root2.cpp hosted with ❤ by GitHub

link(x,y):
連接x與y所在的兩棵樹。
先判斷是否在同一棵splay tree裡，如果是的話就不做任何事
首先Makeroot(x)，x就成為了他所在樹的根。
然後直接把x的父親賦值為y即可。

	inline void link(int x,int y){
	make_root(x);
	node[x].pa=y;
	}

view raw lct_link.cpp hosted with ❤ by GitHub

cut(x,y):
斷開x與y所相連的邊。
首先Makeroot(x)，然後Access(y)，此時x與y在同一棵splay中，再Splay(y)，此時x是y的左兒子，然後將其左兒子及左兒子的父母設成空節點即可。

	inline void cut(int x,int y){
	make_root(x);
	access(y);
	splay(y);
	node[y].ch[0]=0;
	node[x].pa=0;
	}

view raw lct_cut.cpp hosted with ❤ by GitHub

cut_parents(x):
跟cut類似，斷掉x和其父親節點之間的邊。首先access節點x。然後讓x旋轉到所在輔助樹的根節點上。斷掉左子樹。

	inline void cut_parents(int x){
	access(x);
	splay(x);
	node[node[x].ch[0]].pa=0;
	node[x].ch[0]=0;
	}

view raw lct_cut_parents.cpp hosted with ❤ by GitHub

find_root(x):
尋找點x在所在樹的根節點。這個操作很簡單，我們只要對x做一次access操作，這樣x和它的根就應該在一個splay中了。那麼此時的根就應該是這個splay最左邊的節點。
因為是splay tree，所以在搜尋完後仍要進行splay操作

	inline int find_root(int x){
	x=access(x);
	while(node[x].ch[0])x=node[x].ch[0];
	splay(x);
	return x;
	}

view raw lct_find_root.cpp hosted with ❤ by GitHub

對於很多問u到v的路徑問題，我們可以將u到v的路徑構造成一顆splay tree並求出其根節點維護的值即可。

	inline int query(int u,int v){
	/*
	傳回uv路徑splay tree的根結點
	這種寫法無法求LCA
	*/
	make_root(u);
	return access(v);
	}

view raw lct_query.cpp hosted with ❤ by GitHub

如果要不改變根節點的話可以求出LCA再進行處理，以下用u,v路徑上的點權總和為例:

	inline int query_lca(int u,int v){
	/*假設求鏈上點權的總和，sum是子樹的權重和，data是節點的權重*/
	access(u);
	int lca=access(v);
	splay(u);
	if(u==lca){
	return node[lca].data+node[node[lca].ch[1]].sum;
	}else{
	return node[lca].data+node[node[lca].ch[1]].sum+node[u].sum;
	}
	}

view raw lct_query_lca.cpp hosted with ❤ by GitHub

修改點權:

	inline void change(int x,int b){
	splay(x);
	node[x].data=b;
	up(x);
	}

view raw lct_change.cpp hosted with ❤ by GitHub

將一棵有邊權的樹構建成link cut tree:

	struct EDGE{
	int a,b,w;
	}e[10005];
	int n;
	std::vector<std::pair<int ,int > >G[10005];
	/*first表示子節點，second表示邊的編號*/
	int pa[10005],edge_node[10005];
	/*pa是父母節點，暫存用的，edge_node是每個編被存在哪個點裡面的陣列*/
	inline void bfs(int root){
	/*在建構的時候把每個點都設成一個splay tree，不會壞掉*/
	std::queue<int > q;
	for(int i=1;i<=n;++i)pa[i]=0;
	q.push(root);
	while(q.size()){
	int u=q.front();
	q.pop();
	for(int i=0;i<(int)G[u].size();++i){
	int v=G[u][i].first;
	if(v!=pa[u]){
	pa[v]=u;
	node[v].pa=u;
	node[v].data=e[G[u][i].second].w;
	edge_node[G[u][i].second]=v;
	up(v);
	q.push(v);
	}
	}
	}
	}

view raw lct_edge_build.cpp hosted with ❤ by GitHub

查詢這棵樹的邊權，因為不能改變root，所以要對access函數作一點修改，以下以u,v路徑上的最大值為例:

	inline void access(int x,bool is=0){/*is=0就是一般的access*/
	int last=0;
	while(x){
	splay(x);
	if(is&&!node[x].pa){
	printf("%d\n",max(node[last].ma,node[node[x].ch[1]].ma));
	}
	node[x].ch[1]=last;
	up(x);
	last=x;
	x=node[x].pa;
	}
	}

view raw lct_access2.cpp hosted with ❤ by GitHub

查詢只需要這樣寫就好了:

	inline void query_edge(int u,int v){
	access(u);
	access(v,1);
	}

view raw lct_query_edge.cpp hosted with ❤ by GitHub

[ Karatsuba Multiply ] 大數模板乘法Karatsuba法

複雜度大約是$\ord{N^{log3}}$，約為$\ord{N^{1.5}}$比一般直式乘法還快，附上連結:
Karatsuba算法

附模板，配合大數模板使用:

	//operator*的函數用以下這些函數取代
	bigN convert_base(int old_width,int new_width)const{
	vector<long long> p(max(old_width,new_width)+1,1);
	for(size_t i=1;i<p.size();++i)p[i]=p[i-1]*10;
	bigN ans;
	long long cur=0;
	int cur_id=0;
	for(size_t i=0;i<size();++i){
	cur+=at(i)*p[cur_id];
	cur_id+=old_width;
	while(cur_id>=new_width){
	ans.push_back(cur%p[new_width]);
	cur/=p[new_width];
	cur_id-=new_width;
	}
	}
	return ans.push_back(cur),ans.trim(),ans;
	}
	bigN karatsuba(const bigN &b)const{
	bigN res;res.resize(size()*2);
	if(size()<=32){
	for(size_t i=0;i<size();++i)
	for(size_t j=0;j<size();++j)
	res[i+j]+=at(i)*b[j];
	return res;
	}
	size_t k=size()/2;
	bigN a1(begin(),begin()+k);
	bigN a2(begin()+k,end());
	bigN b1(b.begin(),b.begin()+k);
	bigN b2(b.begin()+k,b.end());
	bigN a1b1=a1.karatsuba(b1);
	bigN a2b2=a2.karatsuba(b2);
	for(size_t i=0;i<k;++i)a2[i]+=a1[i];
	for(size_t i=0;i<k;++i)b2[i]+=b1[i];
	bigN r=a2.karatsuba(b2);
	for(size_t i=0;i<a1b1.size();++i)r[i]-=a1b1[i];
	for(size_t i=0;i<a2b2.size();++i)r[i]-=a2b2[i];
	for(size_t i=0;i<r.size();++i)res[i+k]+=r[i];
	for(size_t i=0;i<a1b1.size();++i)res[i]+=a1b1[i];
	for(size_t i=0;i<a2b2.size();++i)res[i+size()]+=a2b2[i];
	return res;
	}
	bigN operator*(const bigN &b)const{
	const static int mul_base=1000000,mul_width=log10(mul_base);
	bigN A=convert_base(width,mul_width);
	bigN B=b.convert_base(width,mul_width);
	int n=max(A.size(),B.size());
	while(n&(n-1))++n;
	A.resize(n),B.resize(n);
	bigN res=A.karatsuba(B);
	res.negative=negative!=b.negative;
	res.carry(mul_base);
	res=res.convert_base(mul_width,width);
	return res.trim(),res;
	}
	bigN operator*(long long b)const{//除法會用到O(N)
	bigN res=*this;
	if(b<0)res.negative=!negative,b=-b;
	for(size_t i=0,is=0;i<res.size()||is;++i){
	if(i==res.size())res.push_back(0);
	long long a=res[i]*b+is;
	is=a/base;
	res[i]=a%base;
	}
	return res.trim(),res;
	}

view raw karatsuba.cpp hosted with ❤ by GitHub