TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

7.7% (1/13)

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

5 2
1 2 5
1 3 3
1 4 6
1 5 7
2 3 4 5

Sample Output

14

Hints

範測中最好的方法是將其朋友都送到1,
所需最大手電筒容量為$2\times$ ($1$到$5$的距離) = $14$

Note:
巡邏員可以巡邏完一人後先回去充電,再去巡邏另一人
巡邏員可直接傳到要監視的人的地窖

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144
1 3000 262144 262144
2 3000 262144 262144
3 3000 262144 262144
4 3000 262144 262144
5 3000 262144 262144
6 3000 262144 262144
7 3000 262144 262144
8 3000 262144 262144
9 3000 262144 262144
10 3000 262144 262144
11 3000 262144 262144
12 3000 262144 262144
13 3000 262144 262144
14 3000 262144 262144
15 3000 262144 262144
16 3000 262144 262144
17 3000 262144 262144
18 3000 262144 262144
19 3000 262144 262144
20 3000 262144 262144
21 3000 262144 262144
22 3000 262144 262144
23 3000 262144 262144
24 3000 262144 262144
25 3000 262144 262144
26 3000 262144 262144
27 3000 262144 262144
28 3000 262144 262144