Background

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.

Problem Description

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.

Input Format

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.

Output Format

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$.

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

8
3
7
6
2
0

Hint

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