P9433 [NAPC-#1] Stage5 - Conveyors

> > >— rs8

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

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.

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

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