P7518 [省选联考 2021 A/B 卷] 宝石

**链的部分分官方数据有误。这里已经修改，如仍有误请反馈。**

欧艾大陆上有 $n$ 座城市，城市从 $1 \sim n$ 编号，所有城市经由 $n - 1$ 条无向道路互相连通，即 $n$ 座城市与 $n - 1$ 条道路构成了一棵树。 每座城市的集市上都会出售宝石，总共有 $m$ 种不同的宝石，用 $1 \sim m$ 编号。$i$ 号城市的集市出售的是第 $w_i$ 种宝石，一种宝石可能会在多座城市的集市出售。 K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多 $c$ 颗宝石，其收集宝石的顺序为：$P_1, P_2, \ldots , P_c$。更具体地，收集器需要先放入第 $P_1$ 种宝石，然后才能再放入第 $P_2$ 种宝石，之后再能放入第 $P_3$ 种宝石，以此类推。其中 $P_1, P_2, \ldots , P_c$ 互不相等。 K 神到达一个城市后，如果该城市的集市上出售的宝石种类和当前收集器中需要放入的种类相同，则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中；否则他只会路过该城市什么都不做。 现在 K 神给了你 $q$ 次询问，每次给出起点 $s_i$ 与终点 $t_i$，他想知道如果从 $s_i$ 号城市出发，沿最短路线走到 $t_i$ 号城市后，他的收集器中最多能收集到几个宝石？（在每次询问中，收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集）

无

无

**【数据范围】** 对于所有测试数据：$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$。 每个测试点的具体限制见下表： | 测试点编号 | $n, q \le$ | 特殊限制 | |:-:|:-:|:-:| | $1 \sim 2$ | $10$ | 无 | | $3 \sim 5$ | $1000$ | 无 | | $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$ | 无 |