3582. [统一省选 2021]宝石

【题目描述】

欧艾大陆上有 $n$ 座城市，城市从 $1\sim n$ 编号，所有城市经由 $n-1$ 条无向道路互相连通，即$ n$ 座城市与 $n-1$ 条道路构成了一棵树。

每座城市的集市上都会出售宝石，总共有 $m$ 种不同的宝石，用 $1\sim m$ 编号。$i$ 号城市的集市出售的是第 $w_i$ 种宝石，一种宝石可能会在多座城市的集市出售。

K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多 $c$ 颗宝石，其收集宝石的顺序为：$P_1 ,P_2 ,\cdots,P_c$ 。更具体地，收集器需要先放入第 $P_1$ 种宝石，然后才能再放入第 $P_2$ 种宝石，之后再能放入第 $P_3$ 种宝石，以此类推。其中 $P_1 ,P_2 ,\cdots,P_c$ 互不相等。

K 神到达一个城市后，如果该城市的集市上出售的宝石种类和当前收集器中需要放入的种类相同，则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中；否则他只会路过该城市什么都不做。

现在 K 神给了你 $q$ 次询问，每次给出起点 $s_i$ 与终点 $t_i$ ，他想知道如果从 $s_i$ 号城市出发，沿最短路线走到 $t_i$ 号城市后，他的收集器中最多能收集到几个宝石？（在每次询问中，收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集）

【输入格式】

第一行包含三个正整数 $n,m,c$，分别表示城市数，宝石种类数，收集器的容量。

第二行包含 $c$ 个正整数 $P_i$ 。数据保证 $1\leq P_i\leq m$ 且这些数互不相等。

第三行包含 $n$ 个正整数 $w_i$ ，表示每个城市集市上出售的宝石种类。

接下来 $n-1$ 行，每行两个正整数 $u_i ,v_i$ ，表示一条连接 $u_i$ 和 $v_i$ 号城市的道路。

第 $n + 3$ 行包含一个正整数 $q$ 表示询问次数。

接下来 $q$行，每行两个正整数 $s_i ，t_i$ 表示该次询问的起点与终点。

【输出格式】

按输入顺序输出 $q$ 行，每行一个整数表示询问的答案。

【样例1输入】

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

【样例1输出】

2
2
2
3
1

【输入输出样例2/3】

输入输出样例2/3

【数据规模与约定】

对于所有测试数据：$1\leq n,q\leq 2\times 10^5,1\leq c\leq m\leq 5\times 10^4,1\leq w_i\leq m$。

每个测试点的具体限制见下表：

【来源】

2021统一省选A卷 Day2 Task1