因為code太多容易顯示不出來，這裡有Gist連結
動態樹，一種支持斷邊、連邊的資料結構（要保證是樹或森林），可以維護路徑、但不能維護子樹。
類似於
樹鏈剖分（建議先學完樹鏈剖分，再學LCT）。
只不過樹鏈剖分的輕重邊是根據子樹大小而決定的，這棵樹只能是靜態的。
而LCT中的“輕重邊”是根據最後一次操作決定的，最後一次處理了x這個點，那麼從x到根的路徑就是重鏈（每個父親只與一個兒子的連邊為重邊）。
用splay來維護每一條重鏈，以點的深度為關鍵字，即splay中的每個點左兒子深度都比他小，右兒子的深度都比他大（若只有一個點，那麼這個點單獨是一棵splay）。
如果還不知道splay tree的可以參考這裡
splay tree及其節點的一些函數:
定義：
- Preferred child：
如果一個點是他父親結點的所有兒子中最後被訪問的，那麼他是他父親的Preferred child。
每個點最多有一個Preferred child。如果x結點是最後被訪問的點，那麼他沒有Preferred child。
- Preferred edge:
每個點到自己的Preferred child的邊叫Preferred edge（相當於樹鏈剖分中的重邊）
- 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都被拋棄。
有了access操作後，其他的操作就更容易實現了
make_root(x):
將x設為其所在的樹的根
首先access(x)，這樣x與根結點處在同一棵splay中。
設a=access(x)，而a是splay tree的根，因為要讓x成為整棵樹的根，所以x的深度要最小，我們只要在a上加一個區間反轉的標記rev就可以完成。
這裡提供兩種方式，最後都會把節點x轉到splay tree根的位置(這很重要)
1.
2.
link(x,y):
連接x與y所在的兩棵樹。
先判斷是否在同一棵splay tree裡，如果是的話就不做任何事
首先Makeroot(x)，x就成為了他所在樹的根。
然後直接把x的父親賦值為y即可。
cut(x,y):
斷開x與y所相連的邊。
首先Makeroot(x)，然後Access(y)，此時x與y在同一棵splay中，再Splay(y)，此時x是y的左兒子，然後將其左兒子及左兒子的父母設成空節點即可。
cut_parents(x):
跟cut類似，斷掉x和其父親節點之間的邊。首先access節點x。然後讓x旋轉到所在輔助樹的根節點上。斷掉左子樹。
find_root(x):
尋找點x在所在樹的根節點。這個操作很簡單，我們只要對x做一次access操作，這樣x和它的根就應該在一個splay中了。那麼此時的根就應該是這個splay最左邊的節點。
因為是splay tree，所以在搜尋完後仍要進行splay操作
對於很多問u到v的路徑問題，我們可以將u到v的路徑構造成一顆splay tree並求出其根節點維護的值即可。
如果要不改變根節點的話可以求出LCA再進行處理，以下用u,v路徑上的點權總和為例:
修改點權:
將一棵有邊權的樹構建成link cut tree:
查詢這棵樹的邊權，因為不能改變root，所以要對access函數作一點修改，以下以u,v路徑上的最大值為例:
查詢只需要這樣寫就好了:
