FTOUR2 - Free tour II

题意翻译

给定一棵n个点的树,树上有m个黑点,求出一条路径,使得这条路径经过的黑点数小于等于k,且路径长度最大

题目描述

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_.

输入输出格式

输入格式


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) two-way 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).

输出格式


Only one number, the maximum total interest value we can obtain.

输入输出样例

输入样例 #1

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

输出样例 #1

12