說到樹鏈剖分，其實故事還挺多的。我記得在高中的OI經(jīng)歷中，我曾無數(shù)次聽到這個名詞，各種省賽、邀請賽貌似都會考這個東西，那時我覺得樹鏈剖分深不可測，是我等蒟蒻不能理解的東西……然后我還記得，某年(好像是NOip2014?)有一題貌似也要用樹鏈剖分。總之是被虐的一B，然后現(xiàn)在覺得這個東西也沒什么難的……

        好吧，言歸正傳。所謂樹鏈剖分其實就是樹的輕重鏈剖分，而樹鏈就是指從某一父節(jié)點一直到葉子節(jié)點的一條鏈。下面先介紹幾個概念：

                1、重兒子：父節(jié)點的所有兒子中，子樹節(jié)點數(shù)目最多的兒子

                2、重邊：連接父節(jié)點和兒子的邊

                3、重鏈：從父節(jié)點往下所有重兒子連在一起的鏈

        有了這些定義，我們就能顯而易見的發(fā)現(xiàn)：任何節(jié)點都只屬于一條樹鏈。然后按照這樣把一棵樹剖分成這樣一條一條的樹鏈，樹鏈剖分就完成了，如圖：

其中這棵樹被剖分成了紅、綠、藍三條鏈，但是要注意，圈出來的兩條邊其實是不屬于樹鏈的。是的完成了這個，樹鏈剖分就已經(jīng)做完了。其實剖分很容易理解，但是問題是這樣做了有什么用呢？這個坑我們后面填~接下來先說說如何實現(xiàn)它。

        第一步當然是對于每個非葉子節(jié)點都要選取一條重邊以及重兒子，這就是重鏈的延伸方向。如你所想，用dfs很容易實現(xiàn)，依次遍歷該節(jié)點的子樹，然后挑選可達深度最大的點作為重兒子，具體代碼如下：

inline void dfs1(int u, int f, int d)			//u為當前節(jié)點，f為父親，d為當前深度{    dep[u] = d;						//先記下深度    size[u] = 1;					//size[]表示子樹的節(jié)點數(shù)目    son[u] = 0;						//son[]表示重兒子    fa[u] = f;    efor(i,u)						//遍歷子樹	{        int ff = g[i].y;        if (ff == f) continue;        dfs1(ff, u, d + 1);        size[u] += size[ff];        if (size[son[u]] < size[ff]) son[u] = ff;	//選取節(jié)點數(shù)最多的點作為重兒子    }}
        標記完重兒子后，我們要把每條鏈連起來，真正形成鏈。那么，我們用什么表示一條鏈呢？我們知道，樹狀數(shù)組、線段樹、平衡樹都是能支持在一段區(qū)間里維護性質(zhì)，若我們能把一條鏈上的節(jié)點弄在一段連續(xù)的區(qū)間中，那我們就容易處理這些問題了。于是便想到了對每個節(jié)點進行重(chong)標號，一條鏈上的點的新編號一定是連續(xù)的，具體的還是利用dfs來實現(xiàn)，代碼：
inline void dfs2(int u, int tp)				//tp表示當前樹鏈的鏈頭，其實這個操作應(yīng)該叫l(wèi)abel{    top[u] = tp;					//top[]表示節(jié)點i所屬樹鏈的鏈頭，方便查詢和修改    id[u] = ++num;					//id[]表示一個節(jié)點新的id(編號)    Rank[id[u]]=u;					//Rank[]表示新編號i對應(yīng)原來的編號，即Rank[id[i]]=i    if (son[u]) dfs2(son[u], tp);			//先對同一條鏈上的重兒子標號    efor(i,u)	{        int ff = g[i].y;        if (ff == fa[u] || ff == son[u]) continue;        dfs2(ff, ff);					//對其他兒子標號    }}
        這樣通過dfs1和dfs2，我們就完成了樹鏈剖分，現(xiàn)在開始填坑……
        樹鏈剖分適合解決樹上的一些修改詢問以及求LCA之類的問題，同過把樹進行剖分，我們可以用很多數(shù)據(jù)結(jié)構(gòu)維護每一條鏈，然后再通過求LCA，我們可以解決對于樹上任意兩點的詢問問題。例如不斷的對邊權(quán)修改，求任意兩點之間的最大邊或最大值，這就可以用線段樹對每個樹鏈進行維護。另外，還值得一提的是樹鏈剖分后求LCA的方法，由于我們在dfs2的時候記錄了top[]數(shù)組，所以用樸素法就能很快的求出LCA，代碼：
inline int LCA(int u, int v){    int tp1 = top[u], tp2 = top[v];			//tp為鏈頭    while (tp1 != tp2)    {        if (dep[tp1] < dep[tp2])			//判斷深度	{            swap(tp1, tp2);            swap(u, v);        }        u = fa[tp1];					//每次向上走了tp1所以速度很快        tp1 = top[u];    }    return tp1;}
        令我不滿意的是，我好像還是沒有說清楚具體如何進行修改和查詢，好吧，下次結(jié)合具體的題目再說把，再給自己挖一個坑……
        最后說說我最不擅長的復(fù)雜度吧，由于是按照輕重鏈剖分的，所以有這樣的定理：
                1、對于輕邊(u,v)，size[v]<=size[u]/2
                2、從根到某一點的路徑上，不超過logN條輕邊
                3、重鏈總數(shù)不超過logN
        因此剖分的時間復(fù)雜度為O(N)；用數(shù)據(jù)結(jié)構(gòu)去維護每一條鏈時，每次的時間復(fù)雜度為O(logN)，當然你若不是用高級數(shù)據(jù)結(jié)構(gòu)我也沒辦法咯=_=……，所以總的來說時間復(fù)雜度是O(NlogN)級別的。
        最后，我又看了一下百度，我覺的百科說的還是更有道理，樹鏈剖分是用來維護樹的路徑信息的一種算法？數(shù)據(jù)結(jié)構(gòu)？我還是不來定義了……
        對了，那個坑我會填的^_^~~~