[ Edmonds's general graph matching algorithm ] 一般圖最大匹配

關於匹配的教學我全部寫在這份投影片裡了:https://jacky860226.github.io/general-graph-weighted-match-slides/#/
所以這裡直接提供模板:
注意這裡必須要是無向圖

[ 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]]中，最小深度的時間戳經過的那個點
查詢:
RMQ的部分就要自己維護了，使用線段樹效能會非常差，在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多

[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表，pa[i][x]表示x的第\(2^i\)的祖先，若不存在則為\(-1\)，可以在DFS或BFS的過程中求得，複雜度為\(\ord{N*MAX\_LOG}\)

對於每筆詢問，我們可以利用剛剛求得的倍增表，在\(\ord{MAX\_LOG}\)的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度，之後二分搜LCA的位置
附上模板:

[ Lowest Common Ancestor , LCA Tarjan's Algorithm ] 最近共同祖先tarjan演算法

tarjan算法的步驟是(當dfs到節點u時):

在並查集中建立僅有u的集合,設置該集合的祖先為u
對u的每個孩子v:

1. 遞迴處理v
2. 合併v的集合到父節點u的集合,確保集合的祖先是u

設置u為已遍歷
處理關於u的查詢,若查詢(u,x)中的x已遍歷過,則LCA(u,x) = x所在的集合的祖先

因為只進行過一次DFS，所以複雜度為\(\ord{(N+Q)*\alpha(N)}\)，為了優化並查集，這裡採用啟發式合併，因此為了記錄集合的祖先而外增加了一個數組head
其雖為線性，但是效率並不怎麼好，跟倍增法的效能差不多
使用方法也很簡單，只需要將每個詢問的兩點記錄起來即可

[ 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的過程中完成:

若樹鏈剖分的目的只是為了求LCA，build_link()及find_lca()有更好的做法:
這就只需進行一次DFS