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