學習筆記 樹鏈剖分

• 2019 年 10 月 10 日
• 筆記

　樹鏈剖分筆記　　

　　咕咕咕了兩個月的blog復活了！

　　（優秀的blog怎麼可以沒有表情包）

　　（這個貓貓超級可愛的！！！）

　　身為一個蒟蒻，就要有自知之明，NOIP寫暴力，所以Lbmttw_lx就要學習各種各樣比較神奇的數據結構和演算法了，昨天在coldhac和Supreme_Ariy的幫助下終於寫完了樹鏈剖分，來寫寫這個筆記鞏固一下新知吧！

　First Part

　　首先我們需要知道為什麼要進行樹鏈剖分，以及樹鏈剖分的適用範圍。樹鏈剖分一般應用於點權樹，對於一棵樹上的節點的點權進行一系列操作。我們先想這個問題，如果是區間的區間修改查詢，我們顯然可以用樹狀數組或者線段樹維護，時間複雜度可以優化到log級別的。現在還是區間修改，單點修改，或者是區間查詢，不過問題不在一個平整的區間上，而是變更到了一棵樹上，我們考慮，樹和一段連續的序列的區別，當樹的根的出度為0且樹退化為一條鏈的時候，就是一個序列了，我們就可以用線段樹求解了，但是問題是大部分的時候樹都不是鏈，這個時候，我們可以用樹鏈剖分將樹剖分成若干條鏈，在線段樹上的體現就是若干段連續的區間，對於這個節點或者路徑的操作，我們就可以轉移到線段樹上進行操作了。

　Second Part

　　樹鏈剖分的時間複雜度為nlogn^2。1e5的數據可以過，但是常數巨大，會被1e6的數據制裁掉（就像是線段樹一樣，一樣過不了1e6的數據）

　　介紹樹鏈剖分中的幾個名詞，size[u]為記錄以節點u根的子樹大小，重兒子：在節點u中所有兒子中size值最大的那個兒子。重邊：連接重兒子與根節點之間的邊，輕邊：根節點到其他兒子之間的邊

　　幾個比較常用的性質：1.如果(u,v)為輕邊，則一定滿足，size[v]<=size[u]/2。證明過程：感性理解size的定義，重兒子的定義，因為重兒子根節點所有兒子中size值最大的那個，所以輕兒子的size一定小於或者等於它父親的size/2

　　　　　　　　　　　　2.從根節點u出發到任意一個節點V的路徑上，經過的輕邊一定不多於logn個。證明：由於性質一可知，size[v]<=size[u]/2，每次經過一條輕邊，它的size值至少/2，所以至多經過nlogn條輕邊就可以到達v

　　　　　　　　　　　　3.我們稱一條路徑為重路徑當且僅當這條重路徑上的所有邊都是重邊，特殊的，一個點也算一條重路徑。那麼對於任意一個點，到根節點的路徑中，至多有logn條重路徑和logn條輕邊，證明：因為每條重路徑的起點和終點都是由輕邊構成（反證法，如果不是輕邊的話，這條重路徑就可以繼續延伸，就說明這並不是終點或者起點，故此命題不成立。得證：每條重路徑的起點和重點都是由輕邊構成），由於性質2可得，至多有logn條輕邊，所以至多有logn條重路徑

　　　　　　　　　　　　4.一個點在且只在一條重路徑上，而每條重路徑也只能由根節點方向向下延展，因為每一個非葉子節點有且只有一個重兒子。

　Third Part

　　我們需要對一棵樹進行輕重鏈的剖分，剖分之後，我們考慮做出以下修改1.對於節點x-節點y的最短路徑加上z  2.求出節點x-節點y的最短路徑上點權之和 3.對於節點x-根節點的路徑上所有點的權值都加上z 4.求出節點x-根節點的路徑上所有點權之和。我們考慮所要處理的路徑（u，v）我們可以分別處理這兩個點到其最近公共祖先的路徑，根據性質3可知，最多分解成logn條輕邊和logn條重路徑，那麼我們現在只需要考慮如何維護這兩個對象。對於重路徑，我們此時可以將其看做是一個序列，只需要線段樹進行維護，而對於輕邊呢，我們可以直接跳過，訪問下一條重路徑，因為輕邊的兩個端點一定在某兩條重路徑。這兩種操作的時間複雜度為logn^2和logn。所以總的時間複雜度為logn^2

　　考慮如何進行輕重鏈的剖分，可以通過兩次dfs來實現。以下為參考

inline void dfs1(int u,int fa)  {      f[u]=fa,deep[u]=deep[fa]+1;sizze[u]=1; int maxx=0;      for(int i=head[u];i;i=g[i].nxt){          int to=g[i].to;          if(to!=fa){              dfs1(to,u); sizze[u]+=sizze[to];              if(sizze[to]>maxx) maxx=sizze[to],son[u]=to;          }      }  }

dfs1

　　dfs1主要計算的是size,son,deep,fa具體的意義應該都知道，son[u]為u的重兒子，以u-son[u]為重邊

 1 inline void dfs2(int u,int topf)   2 {   3     static int cnt=0;   4     dfn[u]=++cnt;a[cnt]=aa[u];top[u]=topf;   5     if(son[u]) dfs2(son[u],topf);   6     for(int i=head[u];i;i=g[i].nxt){   7         int to=g[i].to;   8         if(to!=f[u]&&to!=son[u]) dfs2(to,to);   9     }  10 }

dfs2

　　dfs2主要計算的是top,dfn以及aa，其意義如下，top為x所在的重路徑的頂部頂點，dfn為dfs序，主要維護的是鏈能在線段樹上有連續的下標，這樣就可以用線段樹維護了。aa的意義是節點u在線段樹中的權值。

　例題https://www.luogu.org/problem/P3384樹鏈剖分的模板

　　我們沒有說到的，只有對於鏈的操作了，（操作3和4可以直接基於線段樹實現），考慮如何維護1操作和2操作，我們可以類似於求LCA那樣，不斷的往上跳，然後對於目前的該節點的dfn值，不斷的求和，直到跳到同一個deep上，即跳到了同一個top，求和這樣，權值相加同理。

　　那麼我們就附上這道題操作2和操作1的程式碼吧23333

inline void add_link(int x,int y,int z)  {      while(top[x]!=top[y]){          if(deep[top[x]]<deep[top[y]]) swap(x,y);          modify(1,dfn[top[x]],dfn[x],z);x=f[top[x]];      }      if(deep[x]>deep[y]) swap(x,y);modify(1,dfn[x],dfn[y],z);  }  inline int sum_link(int x,int y)  {      ll ans=0;      while(top[x]!=top[y]){          if(deep[top[x]]<deep[top[y]]) swap(x,y);          ans+=getsum(1,dfn[top[x]],dfn[x]);x=f[top[x]];      }        if(deep[x]>deep[y]) swap(x,y); ans+=getsum(1,dfn[x],dfn[y]);      return ans%mo;  }

　　Thanks！