Problem D
Travelling Caterpillar

Traversing directly between leaves is both dangerous and illegal.
Picture by Vengolis via Wikimedia Commons, CC BY-SA 4.0

Lilith is a hungry caterpillar! From her vantage point at the root of a tree, she has identified some leaves she wishes to munch before returning to the root. She wants to finish munching all of them as quickly as possible so that she will grow into a plump, buttery butterfly.

The tree Lilith occupies is a bit unusual. We can view it as a collection of nodes, where some of the nodes contain leaves that Lilith wishes to munch. Each branch connects exactly two nodes together. It is guaranteed that between every pair of nodes, there is precisely one way to travel from one to the other.

Given a description of the tree and which nodes have leaves that Lilith wishes to munch, can you help Lilith route her munching by minimizing the time she must travel?

\includegraphics[width=0.6\textwidth ]{tree.pdf}
Figure 1: Illustration of Sample Input $1$. Lilith can munch the nodes at leaves $2, 3, 6$ and return to the root $0$ by following the following sequence of nodes: $0 \rightarrow 4 \rightarrow 6 \rightarrow 4 \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 1 \rightarrow 0$. The total distance Lilith travels is the length of each branch she crossed in this sequence: $2+3+3+2+5+1+1+4+4+5 = 30$.


The first line of input contains two integers $N$ ($1 \leq N \leq 1000$), which is the number of nodes in the tree, and $K$ ($1 \leq K \leq N$), which is the number of leaves to be munched.

The next $N-1$ lines of input describe the branches (edges) of the tree. The $i$th such line contains three integers $s_ i$, $t_ i$ ($0 \le s_ i, t_ i < N, s_ i \neq t_ i$), and $d_ i$ ($0 \le d_ i \le 10^6$). This indicates there is a branch between node $s_ i$ and node $t_ i$ which takes $d_ i$ time to cross. Furthermore, if we view the tree as rooted at node $0$, we have that $s_ i$ is the parent of $t_ i$ (i.e. $s_ i$ lies on the unique path from $0$ to $t_ i$). Lilith always starts at the root node $0$.

The last line of input contains $K$ distinct integers $a_1, \ldots , a_ K$ ($0 \leq a_ i < N$), which indicates the nodes containing leaves that Lilith wants to munch.


Display the length of the shortest path along the branches of the tree, starting and ending at the root, which allows Lilith to eat all leaves.

Sample Input 1 Sample Output 1
7 3
0 1 5
0 4 2
1 2 1
1 3 4
4 5 3
4 6 3
2 3 6
Sample Input 2 Sample Output 2
6 3
0 1 5
1 2 5
2 3 42
2 4 347
2 5 612
3 4 5
Sample Input 3 Sample Output 3
3 2
0 1 0
0 2 21
1 2

Please log in to submit a solution to this problem

Log in