FTOUR2  Free tour II
After the success of 2nd anniversary (take a look at problem FTOUR for more details), this 3rd year, Travel Agent SPOJ goes on with another discount tour.
The tour will be held on ICPC island, a miraculous one on the Pacific Ocean. We list N places (indexed from 1 to N) where the visitors can have a trip. Each road connecting them has an interest value, and this value can be negative (if there is nothing interesting to view there). Simply, these N places along with the roads connecting them form a tree structure. We will choose two places as the departure and destination of the tour.
Since September is the festival season of local inhabitants, some places are extremely crowded (we call them crowded places). Therefore, the organizer of the excursion hopes the tour will visit at most K crowded places (too tiring to visit many of them) and of course, the total number of interesting value should be maximum.
Briefly, you are given a map of N places, an integer K, and M id numbers of crowded place. Please help us to find the optimal tour. Note that we can visit each place only once (or our customers easily feel bored), also the departure and destination places don't need to be different.
Input
There is exactly one case. First one line, containing 3 integers N K M, with 1 <= N <= 200000, 0 <= K <= M, 0 <= M <= N.
Next M lines, each line includes an id number of a crowded place.
The last (N  1) lines describe (N  1) twoway roads connected N places, form a b i, with a, b is the id of 2 places, and i is its interest value (10000 <= i <= 10000).
Output
Only one number, the maximum total interest value we can obtain.
Example
Input: 8 2 3 3 5 7 1 3 1 2 3 10 3 4 2 4 5 1 5 7 6 5 6 5 4 8 3 Output: 12
Explanation
We choose 2 and 6 as the departure and destination place, so the tour will be 2 > 3 > 4 > 5 > 6, total interest value = 10 + (2) + (1) + 5 = 12
* Added some unofficial cases
hide comments
shimomire:
20161113 15:04:45
What is the output of the following input?


plosive:
20161014 15:04:52
how solve this with use Boundary partition？ 

w703710691d:
20150904 15:55:24
why I always get a re? 

lu:
20150601 17:08:24
the result turned to TLE QAQ 

lu:
20150601 16:03:01
my program passed the following tests but it got WA.I don't know what's wrong 

kid:
20150107 15:17:10
I chanllenged many codes using the following input


yzx:
20120923 07:05:00
answer:6 

Exia_cai:
20120914 08:07:12
here is a test：


谢良:
20110609 12:31:58
300 

Zhao Tao:
20100427 03:13:28
The test data of this problem is somewhat weak. I successfully chanllenged a code which was accepted using the following input:

Added by:  ThanhVy Hua 
Date:  20070928 
Time limit:  0.100s0.443s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Adapted from Preslav Le's problem, first used in Bulgarian OI 07 