?https://codeforces.com/contest/916/problem/E

題意：

有一棵n個(gè)點(diǎn)的樹(shù)，每個(gè)節(jié)點(diǎn)上有一個(gè)權(quán)值wi，最開(kāi)始根為1號(hào)點(diǎn)．現(xiàn)在有3種

類(lèi)型的操作：

? 1 root, 表示將根設(shè)為root.

? 2 u v x, 設(shè)u, v的最近公共祖先為p, 將p的子樹(shù)中的所有點(diǎn)的權(quán)值加上x(chóng).

? 3 u, 查詢u的子樹(shù)中的所有點(diǎn)的權(quán)值和．

對(duì)于類(lèi)型3操作，輸出答案．

題解：

線段樹(shù) + 樹(shù)鏈剖分

樹(shù)鏈剖分的意義在于：由于函數(shù)

int lca(int x,int y)

大量使用，如果不使用樹(shù)鏈剖分，當(dāng)樹(shù)退化為一根鏈時(shí)，

int lca(int x,int y)的復(fù)雜度為O(n), 從而整個(gè)算法的復(fù)雜度為O(n^2)

使用樹(shù)鏈剖分時(shí)，整個(gè)算法的復(fù)雜度為O(nlogn)

該程序的關(guān)鍵點(diǎn)是：

不實(shí)施換根，每次只記錄新根，并注意新根在后續(xù)操作的影響。

主要難點(diǎn)：在不同新根位置下，求包含x，y 的最小子樹(shù)的根節(jié)點(diǎn)

?