全國(guó)賽08.solution過不了多久Crash就要迎來他朝思暮想的暑假在這個(gè)里他計(jì)

1、Crash 的旅行計(jì)劃【問題描述】過不了多久，Crash 就要迎來他朝思暮想的暑假。在這個(gè)暑假里，他計(jì)劃著到火星上旅游。在火星上有 N 個(gè)旅游景點(diǎn)，Crash 用 1 至 N 這 N 個(gè)正整數(shù)對(duì)這些景點(diǎn)標(biāo)號(hào)。旅游景點(diǎn)之間通過雙向道路相連。由于火星的環(huán)境和地球有很大的差異，建立道路的成本也相對(duì)較高。為了節(jié)約成本，只有 N-1 條道路連接著這些旅 游景點(diǎn)，不過可以保證任何兩個(gè)不同的旅游景點(diǎn)都通過路徑相連。Crash 預(yù)先在互聯(lián)網(wǎng)上查閱了這些景點(diǎn)的信息，根據(jù)網(wǎng)上的介紹，他對(duì)每個(gè)景點(diǎn)都有一個(gè)印象值，這個(gè)印象值為一個(gè)整數(shù)。在這個(gè)旅行中，他會(huì)選擇一個(gè)景點(diǎn)作為旅行的開始，并沿著存在的道路到達(dá)其他景點(diǎn)游玩。為

2、了使旅行不顯得乏味，Crash 不會(huì)經(jīng)過同一個(gè)景點(diǎn)超過一次。Crash 還給這次旅行定義了一個(gè)指數(shù)，也就是他經(jīng)過的所有景點(diǎn)的印象值之和。不過Crash 是個(gè)奇怪的小朋友，他對(duì)于景點(diǎn)的印象值會(huì)發(fā)生改變，并且他也沒有決定好應(yīng)該從哪個(gè)景點(diǎn)開始旅行。因此他希望你能寫一個(gè)程序幫他完成一個(gè)簡(jiǎn)單的任務(wù)：根據(jù)當(dāng)前他對(duì)每個(gè)景點(diǎn)的印象值，計(jì)算從某個(gè)景點(diǎn)開始旅行所能獲得的最大的 指數(shù)。【輸入格式】輸入的第一行包含一個(gè)字符和一個(gè)正整數(shù) N，字符為 ABC 中的一個(gè)，用來表示這個(gè)測(cè)試數(shù)據(jù)的類型（詳見下面的數(shù)據(jù)規(guī)模和約定）。第二行包含 N 個(gè)用空格隔開的整數(shù)，第 i 個(gè)整數(shù)表示 Crash 對(duì) i 號(hào)景點(diǎn)的初始印象值。接

3、著有 N-1 行，每行兩個(gè)正整數(shù) a、b(1 a, b N)，表示從 a 號(hào)景點(diǎn)到 b 號(hào)景點(diǎn)有一條無向道路相連。最后是一些指令，指令只會(huì)是以下三種格式：1Change u x (1 u N) 將 u 號(hào)景點(diǎn)的印象值修改為 x。Query u (1 u N) 詢問從 u 號(hào)景點(diǎn)開始能獲得的最大的Done 收到這個(gè)指令后，你的程序應(yīng)該結(jié)束。指數(shù)?！据敵龈袷健繉?duì)于每條 Query 指令，輸出對(duì)應(yīng)的最大指數(shù)。【樣例輸入 1】A 6111365 -4 3 -2 123453 6Query 3Query 4Change 6 10Query 3Change 2 -5Query 3Query 4 Done【

4、樣例輸出 1】7147615【樣例輸入 2】B 512345-4 3 -223451Query 3Change 5 10Query 3Query 2Change 2 2Query 3 Done【樣例輸出 2】411711【數(shù)據(jù)規(guī)模和約定】測(cè)試數(shù)據(jù)分為 ABC 三類，對(duì)于所有的測(cè)試數(shù)據(jù)都滿足：在任何時(shí)候一個(gè)景點(diǎn)印象值的絕對(duì)值不超過 10000，并且輸入的道路一定能滿足題目描述的要求，即使得任意兩個(gè)不同的景點(diǎn)都能通過路徑相連。對(duì)于A 類數(shù)據(jù)（占 20%的分?jǐn)?shù)）滿足：N 和指令的條數(shù)都不超過 1000。 對(duì)于 B 類數(shù)據(jù)（占 40%的分?jǐn)?shù)）滿足：N 和指令的條數(shù)都不超過 100000，且輸入的第 i

5、 條道路，連接著 i 號(hào)景點(diǎn)和 i+1 號(hào)景點(diǎn)（詳見樣例 2）。對(duì)于 C 類數(shù)據(jù)（占 40%的分?jǐn)?shù)）滿足：N 和指令的條數(shù)都不超過 100000，且任何一個(gè)景點(diǎn)到 1 號(hào)景點(diǎn)需要通過的道路條數(shù)不超過 40。【解題】題目大意：給出一棵樹，每個(gè)結(jié)點(diǎn)有一個(gè)權(quán)值，定義 sum(u, v)表示結(jié)點(diǎn) u到結(jié)點(diǎn) v 路徑上經(jīng)過結(jié)點(diǎn)的取值和。要求實(shí)現(xiàn)兩個(gè)操作：1. 修改一個(gè)結(jié)點(diǎn)的權(quán)值。2. 給出結(jié)點(diǎn) u，詢問sum(u, v)的最大值。對(duì)于題目給出的三類數(shù)據(jù)，可以分別設(shè)計(jì)算法去解決。數(shù)據(jù)A 的解法很容易想到：對(duì)于操作一，直接進(jìn)行修改；而操作二可以從 u開始BFS 或 DFS 這棵樹，求出sum(u, v)的所

6、有取值，輸出最大值。這樣做的時(shí)間復(fù)雜度為 O(QN)，空間復(fù)雜度為 O(N)，足以解決 A 類數(shù)據(jù)。數(shù)據(jù) B 中可以看出這棵樹其實(shí)是一條鏈。用 s(i)表示前 i 個(gè)結(jié)點(diǎn)的權(quán)值和，則sum(u, v) = s(v) s(u-1)。對(duì)于詢問，分兩種情況：u v 和 v u。可以發(fā)現(xiàn)就是求 s(i)在0, u-1內(nèi)的最小值和 s(i)在u+1, N內(nèi)的最大值。對(duì)于修改，不難發(fā)現(xiàn)就是u, N內(nèi)的 s(i)都增加一個(gè)相同的數(shù)。這樣，利用線段樹來s(i)就可以在 O(logN)的時(shí)間內(nèi)完成詢問和修改操作。整個(gè)算法的時(shí)間復(fù)雜度為O(QlogN)，空間復(fù)雜度為 O(N)，可以通過全部 B 類數(shù)據(jù)。最后是 C

7、 類數(shù)據(jù)。首先題目中的無根樹變成以 1 號(hào)結(jié)點(diǎn)為根的有根樹，這樣的話每個(gè)結(jié)點(diǎn)的深度都不超過 40。對(duì)于一條 u 到 v 的路徑，在現(xiàn)在的有根樹中會(huì)有一個(gè)“轉(zhuǎn)折點(diǎn)”，也就是 LCA(u, v)。顯然LCA(u, v)是 u 的一個(gè)祖先，由于 u 的深度不超過 40，因此可以枚舉 u 的每一個(gè)祖先。假如 u 的一個(gè)祖先 x 為L(zhǎng)CA，那么問題就是找一個(gè) x 的子孫 v，使得sum(x, v)最大，并且這個(gè) v 不能和 u 在 x 的同一個(gè)。設(shè) down(i)表示 sum(i, x)的最大值，其中 x為 i 的一個(gè)子孫（或者也可以就是 i 本身）。對(duì)于每個(gè)結(jié)點(diǎn) i，用堆它的子結(jié)點(diǎn)的down 值，并且

8、可以發(fā)現(xiàn) down(i)為其子結(jié)點(diǎn)中最大的down 值加上結(jié)點(diǎn) i 的權(quán)值。修改結(jié)點(diǎn) u 的權(quán)值只會(huì)影響到 u 的祖先的 down 值，并且 u 的祖先個(gè)數(shù)不超過 40，因此可以直接對(duì) u 每個(gè)祖先的堆進(jìn)行修改。回答操作的話，不能直接取 down(x)，因?yàn)?v 可能會(huì)和 u 在 x 的同一個(gè)，不過對(duì)于 x了一個(gè)堆，如果堆頂元素就是 u 所在的根，那么就取次大值，否則可以直接取最大值，這樣詢問和修改的時(shí)間復(fù)雜度都為 O(40*logN)。如果忽略 40 這個(gè)大常數(shù)，整個(gè)算法的時(shí)間復(fù)雜度為 O(QlogN)，空間復(fù)雜度為 O(N)，能解決全部 C 類數(shù)據(jù)。其實(shí)本題有一個(gè)對(duì)于任何樹都適用的 O(Q

9、log2N)的算法。考慮到這個(gè)算法比較復(fù)雜，就降低了此題難度，將大范圍的數(shù)據(jù)變成了兩類特殊的數(shù)據(jù)。不過作為解題，這里還是說一下這個(gè)算法。首先將無根樹變?yōu)橛懈鶚洌S便指定一個(gè)結(jié)點(diǎn)作為根），設(shè) size(i)表示結(jié)點(diǎn) i為根的包含的結(jié)點(diǎn)個(gè)數(shù)。邊劃為兩類：輕邊和重邊。對(duì)于每個(gè)結(jié)點(diǎn) i，選擇 size 最大的一個(gè)子結(jié)點(diǎn)，i 到這個(gè)結(jié)點(diǎn)的邊為重邊，剩余的邊為輕邊。一個(gè)例子如下圖所示（粗邊為重邊）：由于經(jīng)過一條輕邊，size 至少擴(kuò)大兩倍，因此從任何一個(gè)結(jié)點(diǎn)到根經(jīng)過的輕邊條數(shù)為 O(logN)。連續(xù)的重邊連成路徑，稱為重路徑，同時(shí)為了處理方便，單獨(dú)的點(diǎn)也看成一條路徑，這樣每個(gè)點(diǎn)都屬于一條重路徑，重路徑之間

10、通過輕邊連接。下面來分析如何回答詢問。從詢問的結(jié)點(diǎn) u 開始到根的路徑會(huì)和一些重路徑相交，根據(jù)前面的分析，可知經(jīng)過的重路徑條數(shù)為 O(logN)。對(duì)于每一條重路徑，其必然會(huì)是從一條輕邊到了這條重路徑的某個(gè)結(jié)點(diǎn)（u 所在重路徑的情況要特殊考慮，不過也基本類似）。和前面一樣，u 到 v 的路徑在有根樹中有一個(gè)轉(zhuǎn)折點(diǎn)，也就是 u 和 v 的 LCA。考慮這個(gè)轉(zhuǎn)折點(diǎn)在當(dāng)前。如下圖，詢問的結(jié)點(diǎn)是 u，通過輕邊(x, y)來到了 x 所在的重路徑（圖中 u 和y 為同一個(gè)結(jié)點(diǎn)）：的重路徑中，要分兩種情況轉(zhuǎn)折點(diǎn)只會(huì)有兩種情況：xu轉(zhuǎn)折點(diǎn)為 x，那么可以順著這條重路徑向下，然后再通過輕邊離開這條重路徑，或者在

11、 x 就通過輕邊離開這條重路徑。第二種情況不能選擇(x, y)這條輕邊離開，所以單獨(dú)考慮。轉(zhuǎn)折點(diǎn)在 x 上方。接著分析如何高效回答以上兩種情況的最優(yōu)值。設(shè) down(i)表示sum(i, x)的最大值，其中 x 為 i 的一個(gè)子孫（或者也可以就是 i 本身）。對(duì)于每條重路徑，用線段樹來。對(duì)于一個(gè)區(qū)間L, R，MaxL、MaxR 和Sum。假如這條重路徑的第 i 個(gè)結(jié)點(diǎn)為v(i)，這條重路徑中結(jié)點(diǎn) i 的位置為r MaxL = maxsum(v(L), v(i-1) + down(v(i) | L i RMaxR = maxsum(v(i+1), v(R) + down(v(i) | L i R Sum = sum(v(L), v(R)(i)，那么：這三個(gè)值都可以通過子區(qū)間的值在 O(1)的時(shí)間內(nèi)計(jì)算。除了用線段樹重路徑，對(duì)于每個(gè)結(jié)點(diǎn) i，一個(gè)堆，其中的元素為不與 i 在同一條重路徑且為 i 子結(jié)點(diǎn)的 down 值，由于這些子結(jié)點(diǎn)都是別的重路徑最上面的結(jié)點(diǎn)，因此它們的 down 值就是那條重路徑中1, len區(qū)間的 MaxL（len 表示重路徑長(zhǎng)度）。不難看出down(i)就是堆頂元素加上 i 的權(quán)值。回到詢問，轉(zhuǎn)折點(diǎn)在 x 上方時(shí)，就是詢問1, r(x)-1的MaxR。轉(zhuǎn)折點(diǎn)為 x并且順著這條重路徑向下時(shí)，就是詢問r(x)+1, len的MaxL。還有一個(gè)特殊情況是轉(zhuǎn)折點(diǎn)為 x