P9432 [NAPC-#1] rStage5 - Hard Conveyors

**Two new groups of hack testdata have been added to this problem.** ---  Harder, so it may be more fragile, so it is easier to break (confirmed). You only spent two hours to instantly clear the main city s1~s10, and now you are here to instantly clear the reverse city.

**The difference between this problem and Stage5 is that the definition of a valid path is different** (the bold part in the brief statement is different). ~~(Actually there are also: different samples, different data, different partial scores.)~~ ### Brief Statement You are given an unrooted tree with $n$ nodes and $k$ key nodes on the tree. Each edge has a weight (i.e. the edge length). There are $q$ queries. Each query gives $s, t$, and asks for the shortest length of a path from $s$ to $t$ that passes through **at least one** key node.

The first line contains three positive integers $n, q, k$, representing the number of nodes in the tree, the number of queries, and the number of key nodes. The next $n - 1$ lines each contain three positive integers $u, v, w$, indicating that there is an edge $(u, v)$ in the tree with weight $w$. It is guaranteed that the input forms a tree. The next line contains $k$ pairwise distinct positive integers, representing the indices of the key nodes. The next $q$ lines each contain two positive integers $s, t$, representing a query.

For each query, output one line with one non-negative integer, representing the shortest length of a valid path for this query. Note that a valid path may traverse no edges; in this case, the path length is $0$.

### Constraints upd at `2023-6-25`: Two new groups of hack testdata were added and placed in $\text{Sub}\textsf6$. They do not count toward the score. **This problem uses bundled tests.** $$ \def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c|c} \textbf{Subtask} & \text{测试点编号} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1&1\sim2 & k=n & 5 \r \textsf2&16\sim20 &k=1,n\leqslant10^3,q\leqslant10^3 & 15 \r \textsf3&21\sim25 & n\leqslant10^3,q\leqslant10^3 & 15 \r \textsf4&3\sim7 & q=1 & 15 \r \textsf5&8\sim15 & - & 50 \r \textsf6&26\sim27 & - & 0 \r \end{array} $$ For $100\%$ of the data, $1\leqslant n\leqslant 10^5$, $1\leqslant q\leqslant 10^5$, $1\leqslant k\leqslant n$, $1\leqslant w\leqslant 10^4$, $1\leqslant u,v,s,t\leqslant n$. ### Sample Explanation #1  The bold nodes in the figure are key nodes. For each query, the following is one optimal path (there may be multiple optimal paths): 1. $2\to1\to3$. 2. $2\to1$. 3. $7\to1\to2\to1$. 4. $4\to3\to5$. 5. $6\to2\to6$. 6. $2$ (a valid path may traverse no edges; in this case, the path length is $0$). Translated by ChatGPT 5