本屆NOIP的壓軸題，一如既往的難度爆表。

題目：疫情控制。

（PS :由於題目較長，編輯後添加，不算字數）

【問題描述】（梗概）：

有 n 個城市，用 n-1 條路互連，構成了一棵樹。

1 號城市是樹中的根節點，現在，根節點上爆發了一種危害性極高的傳染病。

爲了不讓疫情擴散到邊境城市，也就是葉子節點，於是派出醫療隊，在一些城市建立檢查點。

目標：從1 號城市到邊境城市的每一條路徑上，都至少要有一個檢查點。

醫療隊可以在有路互連的城市間移動，並在城市中建立檢查點。

一支隊伍只能在一個城市建立檢查點，邊境城市也可以建立檢查點，但1 號城市不能建立檢查點。

醫療隊移動所需時間，等於道路的長度，單位是小時。

一個城市可以駐紮多個醫療隊，不同的醫療隊可以同時移動。

現在，一些城市中已經駐紮有醫療隊。

求解：最少需要多少個小時，才能控制住疫情。

【輸入數據】：

第一行，一個整數 n，表示城市個數；

接下來的 n-1 行，每行 3 個整數：u、v、w，表示從城市 u 到城市 v 有一條長爲 w 的道路。

數據保證輸入的是一棵樹，且根節點編號爲 1。

下一行，一個整數 m，表示醫療隊的個數。

再下一行，有 m 個整數，分別表示 m個醫療隊所駐紮的城市編號，其中任意m≠1。

【輸出格式】：

只有一個整數，表示控制疫情需要的最少時間，如果無法控制疫情則輸出-1。

題目後面，還給出了一些輸入輸出的樣例和解釋。

最後，是這道題的數據範圍。

對於 20%的數據，2≤ n≤ 10；

對於 40%的數據，2 ≤n≤50， w大於0小於 10^5；

對於 60%的數據，2 ≤ n≤1000，w大於0小於 10^6；

對於 80%的數據，2 ≤ n≤10，000；

對於 100%的數據，2≤m≤n≤50，000，w大於0小於 10^9。

這很可能是最近幾年來最難的一道題，思考難度超大。

而且有個很噁心的條件，不能停留在根節點。

寫代碼的時候，一不小心就容易出錯。

這道題的難度，即使在NOIP歷史上，也足可以排進前三名。

至於解題思路……

江寒全力開動腦筋，花了10分鐘時間，才理順了過來。

醫療隊可以同時移動，說明需要的總時間，取決於移動距離最長的醫療隊。

根據題意，需要最小化最大值。

不能用模擬的辦法，容易超過時限。

江寒看懂題意後，第一個念頭就是二分答案。

求最大化最小值，最小化最大值，一般都可用二分答案。

然後，可以在二分之後，使用貪心策略，將所有的醫療隊儘可能上提。

但是，數據範圍太大了，直接一個個“上提”，肯定會導致TLE（超時）。

所以必須優化一下。

這種”往上提“的問題，一般可以用倍增法來優化。

具體到這道題裏，可以用DFS（Depth First Search，深度優先搜索）算法，將需要用到的數值預處理一下，然後再倍增。

在操作時，要時刻注意，不能把醫療隊提升到根節點上……

所以，這道題要想得高分，二分答案、貪心、倍增三種算法，缺一不可。

在歷屆NOIP提高組複賽中，這道題的難度都是數一數二的了。

但會者不難。

對江寒來說，只要有了思路，寫代碼並不存在任何問題。

他全力開動腦力，只用了30分鐘，就寫完了代碼，並調試完畢。

雖然問題順利解決掉了，不過……

江寒揉了揉有點發燙的腦門，忍不住嘆了口氣：“嘖，早知道帶條紅極參過來就好了。”

NOIP比賽是允許帶飲食的。

雖然生吃海蔘、不蘸醬油，可能有點另類和驚世駭俗，可總比享受腦力透支的眩暈感好一些吧？

接下來還有將近1個小時，江寒也沒浪費。

編寫代碼，生成大量測試數據，對自己要提交的代碼，進行了高強度的測試。

測試結果非常不錯，100%的測試數據，都能在時限之內完成。

隨後，江寒仔細檢查了一下各種細節，文件名、大小寫、頭文件引用、輸出數據的格式……

全部弄利索，還差5分鐘收卷。

江寒舉手叫來監考教師，再次提前了一小會兒，上傳了答卷。

至此，本屆NOIP對他來說，就基本宣告結束了。

接下來，回家等着成績公示即可。

根據賽組委的安排，大約7天后，選手們就能在官網上查詢到自己的分數。

交完卷，江寒走出大樓，呼吸着初冬的寒風，心情愉快。

“看你的樣子，發揮得還算不錯？”高俊德第一時間迎上來。

江寒笑了笑：“也算達到了預期目標吧，所有題都做出來了，自己測試也沒發現什麼問題。”

“那就好，這我就心裏有底了。”高俊德十分欣慰。

這還真不是盲目樂觀。

在他看來，以江寒的驚人實力，就算髮揮失常，也基本上一等獎穩穩的。

江寒和老高聊了幾句。

聽說一會兒幾名學生要去放鬆一下，老高也沒橫攔豎擋。

不過……

“去玩可以，我得一路跟着。”老高笑眯眯地說。

江寒灑然一笑：“那當然歡迎的了。”

隨後就拿出手機，給夏雨菲打了過去。

很快電話接通。

“在哪呢？”江寒問。

“陪苗姐、浩哥去談了個合同，然後在逛街……”

夏雨菲把自己上午的行蹤，簡單介紹了一下，然後問：“比賽還順利嗎？”

江寒回答：“還可以。”

夏雨菲俏皮一笑，問：“有多可以呀？”

江寒想了想，說：“會答的都答上來了，答了就能得分，然後，沒發現不會的。”

夏雨菲：“……”

意思就是離滿分不遠了唄？

隨後，她又問起考試內容，江寒挑不那麼硬核的部分，給她講了一些。

夏雨菲只聽了幾句，就有點發懵，但還是很耐心地聽着。

“基本情況就是這樣了。”江寒最後總結。

夏雨菲默然半晌，才長嘆了口氣。

還真是隔行如隔山，雖然江寒已經盡力簡化了，可她能聽懂的部分，還是沒多少……

兩人隨便又聊了幾句。

江寒忽然說：“一會兒我打算參加一下集體活動，跟高老師他們去吃點飯，然後可能去唱K或者打檯球，你要不要一起？”

夏雨菲想了想：“吃飯我就不去了，如果是娛樂活動，我倒是可以給你捧個場，正好在街上溜達也挺無聊的。”

說定了這件事，兩人又開始有一搭、沒一搭閒聊。

臨結束，夏雨菲說苗清瀾也有興趣參加，江寒自然也表示歡迎，並讓她轉告關浩一聲。

還說，這叫寧落一圈，不落一人……

掛了電話沒一會兒，熊磊、李山河、朱達昌先後出來。

邊走這三個還在爭論什麼。

看到江寒，熊磊眼前一亮，連忙說：“大神，你來評評理。”

江寒：“……”

聽了一會兒就明白了，原來是對最後一題產生了爭議。

三人居然使用了三種不同的數據結構，每個人又都認爲自己纔是對的，別人的解法有漏洞。

然後，三人誰也說服不理誰，就一路辯論着走了出來。

江寒讓他們一一說明自己的觀點。

結果聽完三人的辦法後，他就無語了。

三人的做法各有巧妙不同，但無一例外，優化程度都不高，硬套標準算法，沒有任何改進，最多也就能過40%的校驗點。

江寒一個一個詳細分析後，嘆了口氣，說：“所以，你們的做法可以說都對，但也都不對。”

高俊德和賀紋章兩人就在一旁，聽了這話，不禁連連點頭。

那三個人做法的特點和缺陷，江寒能這麼快就看清楚，還講解得深入淺出，一般的算法老師也就這個水平了。

高俊德還好，早就知道江寒猛得一批，有這樣的表現也在意料之中。

賀紋章就徹底驚了，這樣的水平參加NOIP，簡直有點降維打擊的意思……

“Day2不可能有白給的題目，你們能在這道題上拿40分已經不少了。”高俊德安慰了一下手下的兩個“兵”。

老賀也拍了拍熊磊的肩膀：“你今天去之前說過，只要不爆0就是勝利，聽你剛纔的說法，肯定爆不了0了。”

衆人你一言、我一語，議論比賽，總結得失。

李山河、朱達昌各種悔恨。

熊磊倒是還好，他本來也沒期望太高，能有個省三就足以安慰。

話題漸漸轉到，兩天六道題，哪一道比較難。

李山河認爲是最後一道，怎麼弄也只能過20%校驗點。

熊磊覺得昨天第3題比較難，都看不懂題意。

朱達昌則認爲今天第2題最難，優化方式不太容易想到。

三人最後看向江寒，想聽聽他的意見。

江寒認真權衡了一下，搖頭：“兩天的第1題，都挺好做，剩下的4道題，感覺都差不多，沒發現哪道題特別難。”

李山河：“……”

朱達昌：“……”

熊孩子：“……”