本屆NOIP的壓軸題，一如既往的難度爆表。
題目：疫情控制。
（PS :由於題目較長(zhǎng)，編輯後添加，不算字?jǐn)?shù)）
【問(wèn)題描述】（梗概）：
有 n 個(gè)城市，用 n-1 條路互連，構(gòu)成了一棵樹(shù)。
1 號(hào)城市是樹(shù)中的根節(jié)點(diǎn)，現(xiàn)在，根節(jié)點(diǎn)上爆發(fā)了一種危害性極高的傳染病。
爲(wèi)了不讓疫情擴(kuò)散到邊境城市，也就是葉子節(jié)點(diǎn)，於是派出醫(yī)療隊(duì)，在一些城市建立檢查點(diǎn)。
目標(biāo)：從1 號(hào)城市到邊境城市的每一條路徑上，都至少要有一個(gè)檢查點(diǎn)。
醫(yī)療隊(duì)可以在有路互連的城市間移動(dòng)，並在城市中建立檢查點(diǎn)。
一支隊(duì)伍只能在一個(gè)城市建立檢查點(diǎn)，邊境城市也可以建立檢查點(diǎn)，但1 號(hào)城市不能建立檢查點(diǎn)。
醫(yī)療隊(duì)移動(dòng)所需時(shí)間，等於道路的長(zhǎng)度，單位是小時(shí)。
一個(gè)城市可以駐紮多個(gè)醫(yī)療隊(duì)，不同的醫(yī)療隊(duì)可以同時(shí)移動(dòng)。
現(xiàn)在，一些城市中已經(jīng)駐紮有醫(yī)療隊(duì)。
求解：最少需要多少個(gè)小時(shí)，才能控制住疫情。
【輸入數(shù)據(jù)】：
第一行，一個(gè)整數(shù) n，表示城市個(gè)數(shù)；
接下來(lái)的 n-1 行，每行 3 個(gè)整數(shù)：u、v、w，表示從城市 u 到城市 v 有一條長(zhǎng)爲(wèi) w 的道路。
數(shù)據(jù)保證輸入的是一棵樹(shù)，且根節(jié)點(diǎn)編號(hào)爲(wèi) 1。
下一行，一個(gè)整數(shù) m，表示醫(yī)療隊(duì)的個(gè)數(shù)。
再下一行，有 m 個(gè)整數(shù)，分別表示 m個(gè)醫(yī)療隊(duì)所駐紮的城市編號(hào)，其中任意m≠1。
【輸出格式】：
只有一個(gè)整數(shù)，表示控制疫情需要的最少時(shí)間，如果無(wú)法控制疫情則輸出-1。
題目後面，還給出了一些輸入輸出的樣例和解釋。
最後，是這道題的數(shù)據(jù)範(fàn)圍。
對(duì)於 20%的數(shù)據(jù)，2≤ n≤ 10；
對(duì)於 40%的數(shù)據(jù)，2 ≤n≤50， w大於0小於 10^5；
對(duì)於 60%的數(shù)據(jù)，2 ≤ n≤1000，w大於0小於 10^6；
對(duì)於 80%的數(shù)據(jù)，2 ≤ n≤10，000；
對(duì)於 100%的數(shù)據(jù)，2≤m≤n≤50，000，w大於0小於 10^9。
這很可能是最近幾年來(lái)最難的一道題，思考難度超大。
而且有個(gè)很噁心的條件，不能停留在根節(jié)點(diǎn)。
寫代碼的時(shí)候，一不小心就容易出錯(cuò)。
這道題的難度，即使在NOIP歷史上，也足可以排進(jìn)前三名。
至於解題思路……
江寒全力開(kāi)動(dòng)腦筋，花了10分鐘時(shí)間，才理順了過(guò)來(lái)。
醫(yī)療隊(duì)可以同時(shí)移動(dòng)，說(shuō)明需要的總時(shí)間，取決於移動(dòng)距離最長(zhǎng)的醫(yī)療隊(duì)。
根據(jù)題意，需要最小化最大值。
不能用模擬的辦法，容易超過(guò)時(shí)限。
江寒看懂題意後，第一個(gè)念頭就是二分答案。
求最大化最小值，最小化最大值，一般都可用二分答案。
然後，可以在二分之後，使用貪心策略，將所有的醫(yī)療隊(duì)儘可能上提。
但是，數(shù)據(jù)範(fàn)圍太大了，直接一個(gè)個(gè)“上提”，肯定會(huì)導(dǎo)致TLE（超時(shí)）。
所以必須優(yōu)化一下。
這種”往上提“的問(wèn)題，一般可以用倍增法來(lái)優(yōu)化。
具體到這道題裡，可以用DFS（Depth First Search，深度優(yōu)先搜索）算法，將需要用到的數(shù)值預(yù)處理一下，然後再倍增。
在操作時(shí)，要時(shí)刻注意，不能把醫(yī)療隊(duì)提升到根節(jié)點(diǎn)上……
所以，這道題要想得高分，二分答案、貪心、倍增三種算法，缺一不可。
在歷屆NOIP提高組複賽中，這道題的難度都是數(shù)一數(shù)二的了。
但會(huì)者不難。
對(duì)江寒來(lái)說(shuō)，只要有了思路，寫代碼並不存在任何問(wèn)題。
他全力開(kāi)動(dòng)腦力，只用了30分鐘，就寫完了代碼，並調(diào)試完畢。
雖然問(wèn)題順利解決掉了，不過(guò)……
江寒揉了揉有點(diǎn)發(fā)燙的腦門，忍不住嘆了口氣：“嘖，早知道帶條紅極參過(guò)來(lái)就好了。”
NOIP比賽是允許帶飲食的。
雖然生吃海蔘、不蘸醬油，可能有點(diǎn)另類和驚世駭俗，可總比享受腦力透支的眩暈感好一些吧？
接下來(lái)還有將近1個(gè)小時(shí)，江寒也沒(méi)浪費(fèi)。
編寫代碼，生成大量測(cè)試數(shù)據(jù)，對(duì)自己要提交的代碼，進(jìn)行了高強(qiáng)度的測(cè)試。
測(cè)試結(jié)果非常不錯(cuò)，100%的測(cè)試數(shù)據(jù)，都能在時(shí)限之內(nèi)完成。
隨後，江寒仔細(xì)檢查了一下各種細(xì)節(jié)，文件名、大小寫、頭文件引用、輸出數(shù)據(jù)的格式……
全部弄利索，還差5分鐘收卷。
江寒舉手叫來(lái)監(jiān)考教師，再次提前了一小會(huì)兒，上傳了答卷。
至此，本屆NOIP對(duì)他來(lái)說(shuō)，就基本宣告結(jié)束了。
接下來(lái)，回家等著成績(jī)公示即可。
根據(jù)賽組委的安排，大約7天后，選手們就能在官網(wǎng)上查詢到自己的分?jǐn)?shù)。
交完卷，江寒走出大樓，呼吸著初冬的寒風(fēng)，心情愉快。
“看你的樣子，發(fā)揮得還算不錯(cuò)？”高俊德第一時(shí)間迎上來(lái)。
江寒笑了笑：“也算達(dá)到了預(yù)期目標(biāo)吧，所有題都做出來(lái)了，自己測(cè)試也沒(méi)發(fā)現(xiàn)什麼問(wèn)題。”
“那就好，這我就心裡有底了。”高俊德十分欣慰。
這還真不是盲目樂(lè)觀。
在他看來(lái)，以江寒的驚人實(shí)力，就算髮揮失常，也基本上一等獎(jiǎng)穩(wěn)穩(wěn)的。
江寒和老高聊了幾句。
聽(tīng)說(shuō)一會(huì)兒幾名學(xué)生要去放鬆一下，老高也沒(méi)橫攔豎擋。
不過(guò)……
“去玩可以，我得一路跟著。”老高笑瞇瞇地說(shuō)。
江寒灑然一笑：“那當(dāng)然歡迎的了。”
隨後就拿出手機(jī)，給夏雨菲打了過(guò)去。
很快電話接通。
“在哪呢？”江寒問(wèn)。
“陪苗姐、浩哥去談了個(gè)合同，然後在逛街……”
夏雨菲把自己上午的行蹤，簡(jiǎn)單介紹了一下，然後問(wèn)：“比賽還順利嗎？”
江寒回答：“還可以。”
夏雨菲俏皮一笑，問(wèn)：“有多可以呀？”
江寒想了想，說(shuō)：“會(huì)答的都答上來(lái)了，答了就能得分，然後，沒(méi)發(fā)現(xiàn)不會(huì)的。”
夏雨菲：“……”
意思就是離滿分不遠(yuǎn)了唄？
隨後，她又問(wèn)起考試內(nèi)容，江寒挑不那麼硬核的部分，給她講了一些。
夏雨菲只聽(tīng)了幾句，就有點(diǎn)發(fā)懵，但還是很耐心地聽(tīng)著。
“基本情況就是這樣了。”江寒最後總結(jié)。
夏雨菲默然半晌，才長(zhǎng)嘆了口氣。
還真是隔行如隔山，雖然江寒已經(jīng)盡力簡(jiǎn)化了，可她能聽(tīng)懂的部分，還是沒(méi)多少……
兩人隨便又聊了幾句。
江寒忽然說(shuō)：“一會(huì)兒我打算參加一下集體活動(dòng)，跟高老師他們?nèi)コ渣c(diǎn)飯，然後可能去唱K或者打檯球，你要不要一起？”
夏雨菲想了想：“吃飯我就不去了，如果是娛樂(lè)活動(dòng)，我倒是可以給你捧個(gè)場(chǎng)，正好在街上溜達(dá)也挺無(wú)聊的。”
說(shuō)定了這件事，兩人又開(kāi)始有一搭、沒(méi)一搭閒聊。
臨結(jié)束，夏雨菲說(shuō)苗清瀾也有興趣參加，江寒自然也表示歡迎，並讓她轉(zhuǎn)告關(guān)浩一聲。
還說(shuō)，這叫寧落一圈，不落一人……
掛了電話沒(méi)一會(huì)兒，熊磊、李山河、朱達(dá)昌先後出來(lái)。
邊走這三個(gè)還在爭(zhēng)論什麼。
看到江寒，熊磊眼前一亮，連忙說(shuō)：“大神，你來(lái)評(píng)評(píng)理。”
江寒：“……”
聽(tīng)了一會(huì)兒就明白了，原來(lái)是對(duì)最後一題產(chǎn)生了爭(zhēng)議。
三人居然使用了三種不同的數(shù)據(jù)結(jié)構(gòu)，每個(gè)人又都認(rèn)爲(wèi)自己纔是對(duì)的，別人的解法有漏洞。
然後，三人誰(shuí)也說(shuō)服不理誰(shuí)，就一路辯論著走了出來(lái)。
江寒讓他們一一說(shuō)明自己的觀點(diǎn)。
結(jié)果聽(tīng)完三人的辦法後，他就無(wú)語(yǔ)了。
三人的做法各有巧妙不同，但無(wú)一例外，優(yōu)化程度都不高，硬套標(biāo)準(zhǔn)算法，沒(méi)有任何改進(jìn)，最多也就能過(guò)40%的校驗(yàn)點(diǎn)。
江寒一個(gè)一個(gè)詳細(xì)分析後，嘆了口氣，說(shuō)：“所以，你們的做法可以說(shuō)都對(duì)，但也都不對(duì)。”
高俊德和賀紋章兩人就在一旁，聽(tīng)了這話，不禁連連點(diǎn)頭。
那三個(gè)人做法的特點(diǎn)和缺陷，江寒能這麼快就看清楚，還講解得深入淺出，一般的算法老師也就這個(gè)水平了。
高俊德還好，早就知道江寒猛得一批，有這樣的表現(xiàn)也在意料之中。
賀紋章就徹底驚了，這樣的水平參加NOIP，簡(jiǎn)直有點(diǎn)降維打擊的意思……
“Day2不可能有白給的題目，你們能在這道題上拿40分已經(jīng)不少了。”高俊德安慰了一下手下的兩個(gè)“兵”。
老賀也拍了拍熊磊的肩膀：“你今天去之前說(shuō)過(guò)，只要不爆0就是勝利，聽(tīng)你剛纔的說(shuō)法，肯定爆不了0了。”
衆(zhòng)人你一言、我一語(yǔ)，議論比賽，總結(jié)得失。
李山河、朱達(dá)昌各種悔恨。
熊磊倒是還好，他本來(lái)也沒(méi)期望太高，能有個(gè)省三就足以安慰。
話題漸漸轉(zhuǎn)到，兩天六道題，哪一道比較難。
李山河認(rèn)爲(wèi)是最後一道，怎麼弄也只能過(guò)20%校驗(yàn)點(diǎn)。
熊磊覺(jué)得昨天第3題比較難，都看不懂題意。
朱達(dá)昌則認(rèn)爲(wèi)今天第2題最難，優(yōu)化方式不太容易想到。
三人最後看向江寒，想聽(tīng)聽(tīng)他的意見(jiàn)。
江寒認(rèn)真權(quán)衡了一下，搖頭：“兩天的第1題，都挺好做，剩下的4道題，感覺(jué)都差不多，沒(méi)發(fā)現(xiàn)哪道題特別難。”
李山河：“……”
朱達(dá)昌：“……”
熊孩子：“……”