P3950 部落沖突 題解
想練練樹剖，找到了一個不像板子的板子。（題目故事情節(jié)引人入勝）
這里來記錄一下樹剖的一些原理。
樹剖的基本原理就是把一棵很高大的樹分成很多塊，然后使用數(shù)據(jù)結(jié)構(gòu)來維護這么多塊。那么怎么分呢？我們定義對于一個節(jié)點，其兒子中的子樹大小最大的那個兒子被稱為這個節(jié)點的重兒子，其他兒子被稱為輕兒子。那么在一棵樹上，一定有很多的重兒子，我們把全部都由重兒子組成的鏈稱為重鏈，都由輕兒子組成的鏈被稱為輕鏈。由此一棵樹被我們分成了很多條重鏈和很多條輕鏈。接著我們考慮如何維護這堆重鏈和輕鏈。
對于某個節(jié)點?，我們定義：
?以?
?為根的子樹節(jié)點個數(shù)。
?
?
?
?
?
）
然后接下來的很多東西很多算法書上都有了，省掉好多字。
正式進(jìn)入題解部分：
我們考慮每個操作的實質(zhì)是什么：
操作 1，也就是詢問，也就是詢問邊權(quán)和是否為?。
操作 2,3 就是修改單條邊。
我們只需要維護每個節(jié)點與其父親的連邊即可。（這種點權(quán)表邊權(quán)的小 trick 應(yīng)該來看這篇文章的人都是會的叭）
Code:
