Background

— rs8

Problem Description

Brief Statement

You are given an undirected tree with $n$ nodes and $k$ key nodes on the tree. The edges have weights (i.e., edge lengths). There are $q$ queries. Each query gives $s, t$ and asks for the minimum length of a path from $s$ to $t$ that visits each key node at least once.

Original Statement

On some level, kid ran into a back-and-forth stage again. Really popular apparently.

The space left for kid by this stage is an undirected weighted tree, where the edge weight is the edge length. The tree has $n$ nodes, and there is exactly one glowing orb on each of $k$ nodes. When kid passes through a node with an orb (called a key node), he can collect the orb. Kid starts from node $s$. When he has collected all $k$ orbs, the portal will appear at node $t$.

Kid wants to speedrun, so he wants to know the minimum time he needs to walk from $s$, collect all $k$ orbs, and enter the portal at $t$ (which is simply the path length, since kid’s speed is constant).

However, Geezer is very cunning. This floor of the tower was copied into $q$ layers, and the $s$ and $t$ in each layer may also change. Kid panicked and hurried to ask you for help.

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$ distinct positive integers, giving the indices of the key nodes.

The next $q$ lines each contain two positive integers $s, t$, representing one query.

Output Format

For each query, output one line with one non-negative integer, representing the minimum length of a valid path for that query.

Note that a valid path may traverse no edges; in that case, the path length is $0$.

7 5 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

8
13
17
22
18

Hint

Constraints

This problem uses bundled testdata.

$$\def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c|c} \textbf{Subtask} & \text{Test Point IDs} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1&1\sim14 & n\leqslant15,\mathbf R& 18 \r \textsf2&15\sim20 & q=1 & 18 \r \textsf3&46\sim48 & s=t,k=n & 6 \r \textsf4&21\sim25 & k=n & 18 \r \textsf5&26\sim30 & \mathbf A & 18 \r \textsf6&31\sim45 & - & 22 \r \end{array}$$

Friendly reminder: $\text{Subtask }\textsf1$ does not restrict the range of $q$.

• Special property $\mathbf R$: The tree is guaranteed to be generated randomly (for $i\ge2$, choose a random node in $[1,i)$ and connect it to $i$, and generate the edge weight uniformly at random within a fixed interval).
• Special property $\mathbf A$: Define $f(x)$ as: there exist $i,j\in[1,n]$ (possibly $i=j$) such that both $i$ and $j$ are key nodes, and $x$ lies on the shortest path from $i$ to $j$. Then, for each query, it is guaranteed that both $f(s)$ and $f(t)$ hold.

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 the key nodes.

For each query, the following is one optimal path (there may be multiple optimal paths):

1. $2\to1\to3$.
2. $2\to1\to3\to1$.
3. $7\to1\to2\to1\to3\to1$.
4. $4\to3\to1\to2\to1\to3\to5$.
5. $6\to2\to1\to3\to1\to2\to6$.

Translated by ChatGPT 5