????樹鏈剖分的思想是通過輕重邊剖分將樹分為多條鏈，保證每個點屬于且只屬于一條鏈（線性結(jié)構(gòu)），然后再通過數(shù)據(jù)結(jié)構(gòu)（如樹狀數(shù)組， SBT，splay，線段樹等）來維護每一條鏈。即非線性結(jié)構(gòu)轉(zhuǎn)變?yōu)榫€性結(jié)構(gòu)。

????樹鏈剖分可以維護樹上路徑信息，每條重鏈就相當于一段區(qū)間，用數(shù)據(jù)結(jié)構(gòu)去維護。把所有的重鏈首尾相接，放到同一個數(shù)據(jù)結(jié)構(gòu)上，然后維護這一個整體即可。

????樹鏈剖分的用處比倍增多，倍增能做的題樹剖一定能做，反過來則否。樹鏈剖分的代碼復(fù)雜度不算特別高，調(diào)試也不難。

樹鏈剖分支持以下操作：

如何劃分樹鏈？

重要性質(zhì)：

• 若 v 是輕兒子， u 是 v 的父親， 則有 size[v] <= size[u] / 2;

• 從根到某一點的路徑上， 不超過 log2n條重鏈，不超過 log2n 條輕邊。