一般來講，我們很熟悉序列的操作，對于樹上路徑的操作會覺得比較棘手。而樹鏈剖分基本思想，是將樹上的路徑問題轉(zhuǎn)化為序列操作問題。
樹鏈剖分，簡單來講即將一棵樹劃分為若干條鏈，然后用數(shù)據(jù)結(jié)構(gòu)去維護每一條鏈。
常見的樹鏈剖分方法為輕/重劃分。
相關(guān)概念
1.對于一棵樹，假設(shè)size(u)代表以u為根的子樹上的節(jié)點個數(shù)，u的兒子節(jié)點為v1,v2,…假設(shè)其中size(vi)是其中最大的，我們稱vi為u的重兒子，其余vj為u的輕兒子。
2.那么u和vi相連的邊為重邊，u和其余兒子節(jié)點相連的邊為輕邊。
3.由重邊鏈接起來的路徑為重鏈（一個點也算一條重鏈），由輕邊鏈接起來的路徑為輕鏈。
如下圖，重邊黑色顯示，其余邊為輕邊。1-2-5-7為重鏈，1-3,2-4為輕鏈。
相關(guān)性質(zhì)
1.如果(u,v)為輕邊，則size(v)<=size(u)/2.
證明：反證法，如果size(v)>size(u)/2，那么v應(yīng)該為重兒子，(u,v)應(yīng)該為重邊。
2.從根到某一點v的路徑上的輕邊條數(shù)不多于O(logn).
證明：首先，到達某個葉子節(jié)點經(jīng)過的輕邊數(shù)量應(yīng)該是最多的，由性質(zhì)1可知，路徑上每經(jīng)過一條輕邊(u,v)，u子樹上的節(jié)點就減少一半。
3.每個點到根上的路徑都有不超過logn條輕邊和logn條（重鏈）重路徑。
證明：根據(jù)性質(zhì)2，每個點到根的路徑一定不會有超過logn條輕邊，觀察圖可以發(fā)現(xiàn)，每一條輕邊的兩個端點一定包含在某兩條重鏈之中，那么重鏈數(shù)量也在logn級別。
輕/重鏈劃分的作用體現(xiàn)？
如果我們對這棵樹進行dfs，優(yōu)先訪問每個節(jié)點的重兒子，并按照每個節(jié)點的發(fā)現(xiàn)時間為其蓋上時間戳。如下圖：
我們可以觀察到兩個特征：
（1）一條重鏈上的節(jié)點其時間戳是連續(xù)的。例如重鏈1-2-5-7時間戳是1,2,3,4
（2）一條輕邊上的兩個節(jié)點一定包含在兩條重鏈中。例如輕邊1-3，節(jié)點分別包含于重鏈1-2-5-7和重鏈3-6中。
現(xiàn)在假設(shè)需要對任意兩點u、v之間的路徑進行處理，例如，我們需要將u、v路徑上所有節(jié)點權(quán)值求和。我們可以分別處理u-lca(u,v),v-lca(u,v)，根據(jù)性質(zhì)3，路徑最多分為logn條重鏈和輕邊。u-v上的所有節(jié)點包含于其中。
（1）對于重鏈，由于其時間戳連續(xù)，相當(dāng)于一個序列，可以用線段樹（或其他數(shù)據(jù)結(jié)構(gòu)）維護。
（2）對于輕邊，可以跳過，因為輕邊的兩個端點包含在2條重鏈之中。
如何實現(xiàn)輕/重鏈劃分？
我們需要維護以下信息：
（1）size[x]:以x為根的子樹節(jié)點個數(shù)。
（2）son[x]:以x為根的子樹，x的重兒子。
（3）father[x]:x節(jié)點的父親
（4）deep[x]:x節(jié)點的深度
（5）top[x]:x節(jié)點所在重鏈的起始節(jié)點。
（6）id[x]:x節(jié)點的訪問次序（優(yōu)先訪問重兒子），代表了其在線段樹中的位置
（7）s[i]:線段樹中位置[i,i]的節(jié)點對應(yīng)樹中哪個節(jié)點。s[id[x]]=x.
我們可以通過兩次dfs完成上述信息的維護，參考代碼如下：
第1次dfs結(jié)束維護信息如下圖：
第2次dfs結(jié)束維護信息如下圖：
如何尋找u、v的lca?
（1）如果top[u]=top[v]，說明u，v在一條重鏈上，那么lca(u,v)為u、v深度較小的點。假設(shè)深度較小的點是u，u到v路徑對應(yīng)了線段樹上的一段區(qū)間[id[u],id[v]]。
（2）如果top[u]!=top[v]，說明u、v在不同重鏈上，他們的lca可能在其中一條重鏈上，也可能在其它重鏈上。假設(shè)top[u]深度>top[v]，那么lca(u,v)一定不會在top[u]上，u可以跳轉(zhuǎn)到father[top[u]]，跳過的這一段重鏈對應(yīng)了線段樹上的一段區(qū)間[id[top[u]],id[u]]；u、v交替跳轉(zhuǎn)最終如果top[u]==top[v]，回到（1），問題得解。
參考代碼如下，函數(shù)ask詢問u、v兩點路徑上節(jié)點的權(quán)值和，query函數(shù)是查詢線段樹的區(qū)間和，線段樹部分此處省略。
參考練習(xí)題目：
ybt1560-1564
