全國賽周而進(jìn)

1、討論一類樹上路徑操作問題周而進(jìn)QTREE題目大意給定N 個(gè)點(diǎn)的樹，需要支持以下2 種操作：1 修改第i 條邊的權(quán)為ti2 查詢點(diǎn)a 到點(diǎn)b 的路徑中的最大邊權(quán)分析經(jīng)典題這里主要提出兩種做法樹鏈劃分動態(tài)樹樹鏈劃分將樹劃分成鏈，從而簡化問題這里提出兩種劃分的方法1 按最長鏈劃分，最壞情況下跨越鏈數(shù)為N2 按子樹大小劃分，最壞情況下跨越鏈數(shù)為logN動態(tài)樹維護(hù)若干顆節(jié)點(diǎn)無序的有根樹森林路徑用一個(gè)平衡二叉樹維護(hù)查找LCA蘋果樹題目大意有一棵蘋果樹，只有1 個(gè)節(jié)點(diǎn)，編號為1，節(jié)點(diǎn)上的蘋果數(shù)量為0。插入節(jié)點(diǎn) 在節(jié)點(diǎn)T 下新增加一個(gè)節(jié)點(diǎn)，蘋果數(shù)量為0修改權(quán)值 將節(jié)點(diǎn)T 上的蘋果數(shù)量修改為D節(jié)點(diǎn)轉(zhuǎn)移 將以節(jié)點(diǎn)

2、S 為根的子樹接到節(jié)點(diǎn)T 上增加權(quán)值 將以T 為根的子樹中所有節(jié)點(diǎn)蘋果數(shù)量增加D詢問以T 為根的子樹中蘋果數(shù)量的最大值詢問以T 為根的子樹中蘋果數(shù)量的總和操作總數(shù)L不超過200000分析維護(hù)dfs序列同一子樹中的點(diǎn)在dfs序中連續(xù)一段INSERT T：插入一對dfs 括號CHANGE T D：直接修改T 對應(yīng)括號的權(quán)值CUT S T：取出S 對應(yīng)區(qū)間，插入到T 下ADD T D：整段修改采用記標(biāo)記的方式，取出T 對以區(qū)間，記上標(biāo)記QMAX T：取出T 對應(yīng)區(qū)間，直接得到最大值QSUM T：取出T 對應(yīng)區(qū)間，直接得到權(quán)值和O(LlogL)otoci題目大意給定n個(gè)點(diǎn)，需要支持以下3種操作1 指定

3、兩個(gè)點(diǎn)之間連一條邊，如果已在同一連通塊就不執(zhí)行2修改一個(gè)點(diǎn)的點(diǎn)權(quán)3查詢兩個(gè)點(diǎn)在樹上路徑的點(diǎn)權(quán)和要求在線算法分析簡述一下就是需要支持樹的合并，以及點(diǎn)權(quán)的維護(hù)。如果不要求在線算法，可以先求出最終的樹（或者森林）的形態(tài)，中途維護(hù)一下連通性解法一由于涉及到樹的合并，所以很容易想到動態(tài)樹我們來依次考慮每一個(gè)操作對于需改點(diǎn)權(quán)很方便，因?yàn)檫@里動態(tài)樹在維護(hù)路徑的時(shí)候本身就是維護(hù)點(diǎn)權(quán)的和對于查詢兩個(gè)點(diǎn)的路徑上的點(diǎn)權(quán)，可以首先求出兩個(gè)點(diǎn)在樹上的LCA，然后也就是簡單的類似樹上路徑求和的問題對于合并操作，假設(shè)這里是將樹A上的點(diǎn)u作為樹B上點(diǎn)v的兒子 首先需要將u提根，也就是將u到根的路徑上的點(diǎn)的位置翻轉(zhuǎn)，然后可以直

4、接連接解法二維護(hù)dfs序列a b e h h e f f b c c d g i i g d a定義e(u)表示到u 入棧時(shí)已經(jīng)入棧的點(diǎn)l(u) 表示u 入棧時(shí)已經(jīng)出棧的點(diǎn)p(u)表示u 到根的距離p(u)=e(u)-l(u)p(u,v)=p(u)+p(v)-p(LCA)合并兩個(gè)樹dfs序有變化暴力重建較小樹的dfs序，插入到較大樹中O(NlogN)network題目大意給定N個(gè)節(jié)點(diǎn)的樹，有Q個(gè)詢問1 修改一個(gè)點(diǎn)的點(diǎn)權(quán)2 查詢兩點(diǎn)路徑上的第k大點(diǎn)權(quán)分析樹鏈劃分維護(hù)dfs序列just for fun題目大意有n個(gè)不連通的城市，有一個(gè)公路修建計(jì)劃每個(gè)城市有不同的發(fā)達(dá)程度，我們記為Wi，初始定義Wi

5、=i。我們約定命令總共有n 個(gè)城市，m 條命令命令為以下3 種格式：1 連接城市ab，如果ab 已經(jīng)連通，不執(zhí)行2 將城市a 的Wa 修改為b bn3 查詢城市a 到城市b 的路徑中w 第k 小的值，4 查詢城市a 到城市b 的路徑上的發(fā)達(dá)程度c 的點(diǎn)權(quán)的乘積模28256292必須設(shè)計(jì)一個(gè)在線算法完成本題分析本題看上去像是前面幾題的綜合版由于動態(tài)樹不能方便處理操作3和操作4,所以這里我們來考慮一下剩下的兩種方法維護(hù)dfs序操作3 查詢兩點(diǎn)之間路徑上權(quán)值第k大的點(diǎn)二分答案，轉(zhuǎn)化為判定性問題判斷路徑上權(quán)值x的點(diǎn)個(gè)數(shù)與otoci一題類似操作4 查詢ab的路徑上的發(fā)達(dá)程度c 的點(diǎn)權(quán)的乘積模28256292模數(shù)不是質(zhì)數(shù)，所以比較棘手樹鏈劃分此題涉及到樹的合并，所以需要?jiǎng)討B(tài)維護(hù)劃分樹鏈塊狀鏈表維護(hù)樹鏈同一塊中點(diǎn)按點(diǎn)權(quán)排序操作1啟發(fā)式合并暴力重構(gòu)較小樹的樹鏈劃分，但合并后影響較大樹的劃分O(NlogNN)操作2修改只涉及一個(gè)塊塊內(nèi)有序暴力修改維護(hù)O(n)操作3二分答案，轉(zhuǎn)化為判定性問題塊完全包含在路徑上，二分查