P7518 [NOI Qualifier Joint Contest 2021 A/B] Gems.

**Some official testdata for the chain part is incorrect. It has been corrected here. If there are still mistakes, please report them.**

On the continent of Oai, there are $n$ cities, numbered from $1$ to $n$. All cities are connected by $n - 1$ undirected roads, meaning the $n$ cities and $n - 1$ roads form a tree. In the market of each city, gems are sold. There are $m$ different types of gems in total, numbered from $1$ to $m$. The market in city $i$ sells gems of type $w_i$. One type of gem may be sold in the markets of multiple cities. God K has a gem collector. This collector can collect at most $c$ gems in order, and the required order is: $P_1, P_2, \ldots, P_c$. More specifically, the collector must first put in a gem of type $P_1$, then it can put in a gem of type $P_2$, then type $P_3$, and so on. Here $P_1, P_2, \ldots, P_c$ are all distinct. After God K arrives at a city, if the type of gem sold in that city's market is the same as the type that the collector currently needs to put in, then he can buy one gem in that market and put it into the collector. Otherwise, he will just pass through the city and do nothing. Now God K gives you $q$ queries. Each query gives a start city $s_i$ and an end city $t_i$. He wants to know: if he starts from city $s_i$ and walks along the shortest path to city $t_i$, what is the maximum number of gems he can collect in his collector? (In each query, the collector initially contains no gems. The gems sold in the markets of the start and end cities can also be tried to be collected.)

The first line contains three positive integers $n, m, c$, representing the number of cities, the number of gem types, and the capacity of the collector. The second line contains $c$ positive integers $P_i$. The data guarantees $1 \le P_i \le m$ and all these numbers are distinct. The third line contains $n$ positive integers $w_i$, where $w_i$ indicates the type of gem sold in the market of city $i$. The next $n - 1$ lines each contain two positive integers $u_i, v_i$, representing a road connecting cities $u_i$ and $v_i$. The next line contains one positive integer $q$, representing the number of queries. The next $q$ lines each contain two positive integers $s_i, t_i$, representing the start city and the end city of the query.

Output $q$ lines in the input order, each containing one integer, representing the answer to the query.

**Constraints** For all testdata: $1 \le n, q \le 2 \times {10}^5$, $1 \le c \le m \le 5 \times {10}^4$, $1 \le w_i \le m$. The specific limits for each test point are shown in the table below: | Test Point ID | $n, q \le$ | Special Constraint | |:-:|:-:|:-:| | $1 \sim 2$ | $10$ | None | | $3 \sim 5$ | $1000$ | None | | $6 \sim 10$ | $2 \times {10}^5$ | $m \le 300$ | | $11 \sim 14$ | $2 \times {10}^5$ | $u_i = i$, $v_i = i + 1$ | | $15 \sim 20$ | $2 \times {10}^5$ | None | Translated by ChatGPT 5