2125 . 殿壬與情人節
TopCoder
Tags
Description
殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲，而現在要講的，是殿壬兩週後的故事。
西洋情人節是殿壬最討厭的節日，看著路上手牽著手的情侶總會另他悲憤不已。為了讓自己在情人節開心一點，殿壬想到了一個計畫。
殿壬決定要在情人節綁架$m$對異性情侶，並且將他們監禁在絕對逃不出的集中營：IOI Camp。IOI Camp是由$n$個地窖及$n-1$條地道組成，地窖編號$1$到$n$，地窖之間由地道連接，且地道中的移動沒有方向限制。殿壬要將這$2m$個人分別關在不同地窖的地牢裡。為了方便管理，保證每個地窖都可以藉由一些地道到達任意一個地窖。
殿壬並不放心，他決定聘請你的朋友共$m$人來擔任巡邏員巡視IOI Camp，每個巡邏員都要負責監視一對男女(他們不一定是情侶)。殿壬會用大魔法師的力量將他們分別傳送到$m$個位在地窖中的巡邏站，完成巡邏任務(走到自己負責監視的男女的地窖)之後，巡邏員必須回到自己初始的巡邏站，這樣殿壬才能再次將他們傳送出IOI Camp。由於整個IOI Camp都在地底下，沒有任何光源，所以巡邏時必須各自攜帶手電筒。為了避免危險，在巡邏員手電筒沒電之前都必須要回到自己起始的巡邏站充電(每支手電筒規格不一定一樣)，最多只能充到該手電筒的電量上限。
為了節省成本，殿壬想知道在最佳化工作分配及巡邏站的架設位置下，這$m$個巡邏員攜帶的手電筒中，最大電量的手電筒電量至少要多少，你能幫幫他嗎？
Input Format
第一行輸入兩個整數$n, m$，代表地窖數目及情侶對數
接下來$n-1$行，每行有三個整數$u_i, v_i, t_i$，表示第$u_i$間地窖到第$v_i$間地窖之間有一條地道，完整走完此地道的手電筒的電量消耗為$t_i$。
最後一行包含$2m$個整數$p_1, p_2, ..., p_{2m}$。若$i \leq m$，表示第$i$位男生被關在第$p_i$間地窖的地牢中；若$i>m$，表示表示第$i - m$位女生關在第$p_i$間地窖的地牢中。
- $2\leq 2\times m\leq n\leq 5\times 10^ 5$
- $1\leq m\leq 300$
- $1\leq u_i,v_i,p_i\leq n$
- $1\leq t_i\leq10^ 9$
Output Format
輸出題目要求的一正整數
Sample Input 1
1 2 5
1 3 3
1 4 6
1 5 7
2 3 4 5
Sample Output 1
Hints
範測中最好的方法是將其朋友都送到1，
所需最大手電筒容量為$2\times$ ($1$到$5$的距離) = $14$
Note:
巡邏員可以巡邏完一人後先回去充電，再去巡邏另一人
巡邏員可直接傳到要監視的人的地窖
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|