樹鍊剖分簡單分析及模闆(雜談)

這幾天學習了一下樹鍊剖分，順便寫一下我的了解、

早上看了一下别人的講解，雲裡霧裡，終于算是搞懂了、

樹鍊剖分是解決在樹上進行插點問線，插線問點等一系列樹上的問題

假如現在給你一棵樹，然後沒兩條邊之間有一條權值，有一些操作，1：x---y之間的最大權值是多少，2：改變x---y之間的權值

當然編号不是簡單的随便編号，如果我們進行随便的編号，然後建立一個線段樹，如果要更新一個邊的權值，是log2（n）的複雜度，而查找的話，我們要枚舉x--y的之間的所有的邊，假如我們随便以一個點為根節點進行編号，最大的長度是樹的直徑，這個值本身是比較大的，而線上段樹上查找任意一個區間的複雜度也是log2（n），這樣查找一次的時間複雜度比直接暴力還要高，是以很明顯是不行的。

那麼就要想想辦法了，我們能不能把x--y之間的一些邊一塊兒查找，這就是關于樹鍊剖分的重邊和輕邊，

重邊：某個節點x到孩子節點形成的子樹中節點數最多的點child之間的邊，由定義發現除了葉子節點其他節點隻有一條重邊

重邊是可以放在一塊兒更新的，而有

性質：從根到某一點的路徑上輕邊、重邊的個數都不大于logn。

是以這樣查找的時間複雜度相當于log2（n）

實作的話很簡單，用兩個dfs處理數數的資訊，重邊以及輕邊，然後就是一些線段樹的操作了。

模闆“：以spoj 375 為例