P9245 [Lanqiao Cup 2023 NOI Qualifier B] Scenic Area Tour Guide

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.

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 $K$ integers. The $i$-th integer represents the time spent on shuttles after skipping $A_{i}$.

**[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