轉載請注明：
【原題】
time limit: 10 sec memory limit: 162 mb
submit: 4465 solved: 1858
[][]
一棵樹上有n個節點，編号分别為1到n，每個節點都有一個權值w。我們将以下面的形式來要求你對這棵樹完成一些操作： i. change u t : 把結點u的權值改為t ii. qmax u v: 詢問從點u到點v的路徑上的節點的最大權值 iii. qsum u v: 詢問從點u到點v的路徑上的節點的權值和 注意：從點u到點v的路徑上的節點包括u和v本身
輸入的第一行為一個整數n，表示節點的個數。接下來n – 1行，每行2個整數a和b，表示節點a和節點b之間有一條邊相連。接下來n行，每行一個整數，第i行的整數wi表示節點i的權值。接下來1行，為一個整數q，表示操作的總數。接下來q行，每行一個操作，以“change u t”或者“qmax u v”或者“qsum u v”的形式給出。 對于100％的資料，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節點的權值w在-30000到30000之間。
對于每個“qmax”或者“qsum”的操作，每行輸出一個整數表示要求輸出的結果。
4
1 2
2 3
4 1
4 2 1 3
12
qmax 3 4
qmax 3 3
qmax 3 2
qmax 2 3
qsum 3 4
qsum 2 1
change 1 5
change 3 6
qmax 2 4
1
2
10
6
5
16
【序言】我可是用樹鍊剖分做的= =樹分治寫起來更麻煩。樹剖我今天剛剛入門= =，寫一篇題解加深印象。
因為腦中還殘存着的沒學之前的一些想法，本教程更适合初學者吧。希望各路大牛也多多指導。
以下内容結合一篇講的不錯的教程，我加了一些改動，更加易懂吧。也請原創大牛釋懷 = =。
【問題】在一棵樹上進行路徑的修改、求極值、求和。
【樹鍊剖分的概念】樹鍊，就是樹上的路徑。剖分，就是把路徑分類為重鍊和輕鍊。樹鍊剖分就是把一些點合成一條路徑，使其線上段樹中的編号（下标）有序，并用線段樹來維護，使得查詢、修改的效率大大提高（有點像莫隊的分塊思想）。假設我們把路徑分好鍊了（先不要在乎是怎麼分的），每次詢問兩個點對（x，y）時，若x和y在同一鍊中，直接詢問線段樹中的u和v（因為同一條鍊中下标是連續的）u，v是x，y對應的線段樹中的點。否則的話，我們從深度大的點上一點一點向上爬，每次記錄該點所在的鍊上的情況，直到x，y在同一條鍊上。
【注意】樹鍊剖分中的線段樹中每個點代表的意義可以是原圖的邊或點。這道題是點，我就以點來叙述。
【數組含義簡介】記num[v]表示以v為根的子樹的節點數，deep[v]表示v的深度(根深度為1)，top[v]表示v所在的鍊的頂端節點，f[v]表示v的父親，son[v]表示與v在同一重鍊上的v的兒子節點（姑且稱為重兒子），tree[v]表示節點v線上段樹中的編号，pre[v]表示線段樹中編号是v的節點所對應的原圖中的點（與tree相反）
隻要把這些東西求出來，就能用logn的時間完成原問題中的操作。
【術語解釋】
重兒子：num[u]為v的子節點中num值最大的，那麼u就是v的重兒子。
輕兒子：v的其它子節點。
重邊：點v與其重兒子的連邊。
輕邊：點v與其輕兒子的連邊。
重鍊：由重邊連成的路徑。
輕鍊：輕邊。
剖分後的樹有如下性質：
性質1：如果(v,u)為輕邊，則siz[u]
* 2 < siz[v]；
性質2：從根到某一點的路徑上輕鍊、重鍊的個數都不大于logn。
至于證明吧，我就不證了~~（其實我不會）隻要能應用、并知道複雜度就行了。
【預處理算法實作】
我們可以用兩個dfs來求出fa、deep、num、son、top、tree、pre。
dfs_1：把fa、deep、num、son求出來，比較簡單。
dfs_2：①我們依次标記tree[v]（按搜尋的順序），同時得到pre。
②對于v，當son[v]存在（即v不是葉子節點）時，顯然有top[son[v]] = top[v]。（沒有就退出）
③然後我們先搜尋v的重兒子u，并把u的重兒子、重孫子...的top值也置為top[v]；
④接着我們再搜尋v的輕兒子u，并把u的重兒子、重孫子...的top值置為u；
将樹中各邊的權值線上段樹中更新，建鍊和建線段樹的過程就完成了。
【查詢&修改算法實作】
例如将u到v的路徑上每條邊的權值都加上某值x。
記f1=top[u]，f2=top[v]。
當f1<>f2時：不妨設dep[f1]>=dep[f2]，那麼就更新u到f1的權值(logn)，并使u=f[f1]。
當f1=f2時：u與v在同一條重鍊上，直接更新u到v路徑上的點的權值(logn)，修改完成；
重複上述過程，直到修改完成。
如下圖所示，較粗的為重邊，較細的為輕邊。（輕邊實質上是長度為1的鍊）節點編号旁邊有個紅色點的表明該節點是其所在鍊的頂端節點。藍色數字請無視= =（因為是copy人家圖的，他的線段樹中存的是邊）
假設我們要修改11到10的路徑時。
我們通過11和10的不斷向上爬（具體操作詳見上面），使他們最終在1号點相交。這樣，11隻經過重鍊2--11,10隻經過自己和鍊1--14，效率相當的高。（為什麼覺得有點像ac自動機呢）
【回歸原題】這樣，原題就是裸的樹鍊剖分了。具體注釋看代碼。
【代碼】