P10289 [GESP Sample Problem Level 8] Xiao Yang’s Trip

Related multiple-choice and true/false problems: .

Xiao Yang is preparing to travel to Country B. Country B has $n$ cities, numbered from $1$ to $n$ in order. The cities are connected by $n-1$ bidirectional roads, and any two cities are reachable from each other (that is, there exists a path between any two cities). Xiao Yang can move between cities via bidirectional roads, and traversing one bidirectional road takes $1$ unit of time. In Country B, there are $k$ cities equipped with portals. The indices of the cities with portals are $b_1,b_2, \cdots ,b_k$. From any city that has a portal, Xiao Yang can spend $0$ units of time to go to another city that has a portal. Note: If there is a bidirectional road between two portal cities, Xiao Yang may choose either to travel via the road or to teleport via the portals. Xiao Yang plans to travel in Country B for $q$ trips. For the $i$-th trip ($1 \le i \le q$), Xiao Yang plans to go from city $u_i$ to city $v_i$. You are asked to find the minimum time required.

The first line contains three positive integers $n,k,q$, representing the number of cities in Country B, the number of cities with portals, and the number of trips Xiao Yang plans to make. The next $n-1$ lines each contain two positive integers $x_i, y_i$, indicating a bidirectional road connecting the two cities. The $(n + 1)$-th line contains $k$ positive integers, indicating the indices of the cities with portals. The next $q$ lines each contain two positive integers $u_i,v_i$, indicating the starting city index and the destination city index for Xiao Yang’s $i$-th trip.

Output $q$ lines in total. On the $i$-th line ($1 \leq i \leq q$), output one non-negative integer, representing the minimum time needed for Xiao Yang’s $i$-th trip from city $u_i$ to city $v_i$.

| Subtask | Score | $n \leq $ | $ k \leq $ | $q \leq $ | |:-: | :-: | :-: | :-: | :-:| | $1$ | $30$ | $500$ | $500$ | $1$ | | $2$ | $30$ | $2 \times 10^5$ | $0$ | $2 \times 10^5$ | | $3$ | $40$ | $2 \times 10^5$ | $2 \times 10^5$ | $2 \times 10^5$ | For all testdata, $1 \leq n \leq 2 \times 10^5$, $0 \leq k \leq n$, $1 \leq x_i, y_i, u_i, v_i \leq n$, and $u_i \neq v_i$. Translated by ChatGPT 5