CodeSprintLA 2020 — Team Competition

Start

2020-05-23 09:30 AKDT

CodeSprintLA 2020 — Team Competition

End

2020-05-23 12:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -484 days 15:24:48

Time elapsed

2:30:00

Time remaining

0:00:00

Problem G
Mining Gold!

/problems/codesprintla20.mininggold/file/statement/en/img-0001.jpg
Gold Bar Lot. Photo by Pixabay

It has been a long, tiring week of tests at UCLA. Your friend wants to cheer you up, so he invites you over to his dorm to play a new game he recently purchased: Mining Gold!

In the game, you are the owner of a goldmine. Your underground tunnel network can be represented as a rooted tree with $n$ different checkpoints, with the tree rooted at checkpoint $1$. Each tunnel connects exactly two checkpoints, and has a transportation value, which is the amount of gold that can be gained by travelling through that tunnel between the checkpoints. It turns out, some tunnels are very poorly built so every time you travel through that tunnel you need to use some gold to hire a guide! Thus, some edges may have a negative transportation value.

Your friend is curious about the gold transportation within the goldmine and asks you to answer $q$ queries, where each query gives a single integer $x$ $(1 \leq x \leq n)$. For each integer $x$, your friend asks you, "If you travel along some simple path while staying in the subtree of $x$, what’s the smallest amount of gold you can possibly gain?" In other words, you want to find the minimum sum of transportation values of all the tunnels traveled through if you start at checkpoint $x$ and travel to some checkpoint in its subtree without visiting any checkpoint twice and without ever leaving the subtree of $x$.

Input

The first line of input gives $n$ and $q$ $(1 \leq n, q \leq 2 \cdot 10^5)$, the number of checkpoints and queries, respectively.

The next $n - 1$ lines will give three integers per line in the form $a$ $b$ $c$, denoting an edge between checkpoints $a$ and $b$ $(1 \leq a, b \leq n, a \neq b)$ with transportation value $c$ $(-10^9 \leq c \leq 10^9)$.

The next $q$ lines will give a single integer $x$, the checkpoint in which to process the current query.

Output

Output $q$ lines, where the $i^{th}$ line will contain the answer to the $i^{th}$ query.

Sample Input 1 Sample Output 1
4 4
1 2 -1
2 3 2
2 4 3
4
2
3
1
0
2
0
-1
Sample Input 2 Sample Output 2
1 2
1
1
0
0
Sample Input 3 Sample Output 3
5 5
1 2 1
2 3 -2
3 4 3
4 5 -4
1
2
3
4
5
-2
-3
-1
-4
0