Problem Description

A scenic area has a total of $N$ attractions, numbered from $1$ to $N$. There are $N - 1$ bidirectional shuttle routes between attractions, forming a tree structure. Traveling between attractions can only be done by these shuttles and costs a certain amount of time.

Xiaoming is an experienced tour guide in this scenic area. Every day, he takes tourists to visit $K$ attractions in a fixed order: $A_{1}, A_{2}, \ldots, A_{K}$. Today, due to time limits, Xiaoming decides to skip exactly one attraction and only visit $K - 1$ attractions in order. Specifically, if Xiaoming chooses to skip $A_{i}$, then he will visit, in order, $A_{1}, A_{2}, \ldots, A_{i-1}, A_{i+1}, \ldots, A_{K}$ $(1 \leq i \leq K)$.

For each $A_{i}$, compute how much time Xiaoming needs to spend on shuttle rides between attractions if he skips this attraction.

Input Format

The first line contains $2$ integers $N$ and $K$.

The next $N - 1$ lines each contain $3$ integers $u, v, t$, indicating that there is a shuttle route between attraction $u$ and $v$, and it takes $t$ units of time.

The last line contains $K$ integers $A_{1}, A_{2}, \ldots, A_{K}$, representing the original planned tour route.

Output Format

Output $K$ integers. The $i$-th integer represents the time spent on shuttles after skipping $A_{i}$.

6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1

10 7 13 14

Hint

[Sample Explanation]

The original route is $2 \rightarrow 6 \rightarrow 5 \rightarrow 1$.

When skipping $2$, the route is $6 \rightarrow 5 \rightarrow 1$. Here, $6 \rightarrow 5$ costs $3 + 2 + 2 = 7$, and $5 \rightarrow 1$ costs $2 + 1 = 3$, so the total time is $10$.

When skipping $6$, the route is $2 \rightarrow 5 \rightarrow 1$. Here, $2 \rightarrow 5$ costs $1 + 1 + 2 = 4$, and $5 \rightarrow 1$ costs $2 + 1 = 3$, so the total time is $7$.

When skipping $5$, the route is $2 \rightarrow 6 \rightarrow 1$. Here, $2 \rightarrow 6$ costs $1 + 1 + 2 + 3 = 7$, and $6 \rightarrow 1$ costs $3 + 2 + 1 = 6$, so the total time is $13$.

When skipping $1$, the route is $2 \rightarrow 6 \rightarrow 5$. Here, $2 \rightarrow 6$ costs $1 + 1 + 2 + 3 = 7$, and $6 \rightarrow 5$ costs $3 + 2 + 2 = 7$, so the total time is $14$.

[Constraints and Notes for Test Cases]

For $20\%$ of the testdata, $2 \leq K \leq N \leq 100$.

For $40\%$ of the testdata, $2 \leq K \leq N \leq 10^{4}$.

For $100\%$ of the testdata, $2 \leq K \leq N \leq 10^{5}$, $1 \leq u, v, A_{i} \leq N$, $1 \leq t \leq 10^{5}$. It is guaranteed that all $A_{i}$ are pairwise distinct.

Lanqiao Cup 2023 Provincial Contest B Group, Problem I.

Translated by ChatGPT 5