Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1108.

Problem Description

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.

Input Format

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 Format

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

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

4

5 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3

2
1
4

Hint

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