一碗酸梅湯 作品
第257章 NOIP中最難的題型
本屆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（depthfirstsearch，深度優先搜索）算法，將需要用到的數值預處理一下，然後再倍增。
題目:疫情控制。
（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（depthfirstsearch，深度優先搜索）算法，將需要用到的數值預處理一下，然後再倍增。