#P8339. [AHOI2022] 钥匙

[AHOI2022] 钥匙

题目描述

nn 座城市,编号为 1,2,,n1, 2, \ldots, n。这些城市由 n1n - 1 条无向道路相连,每条无向道路连接两座城市,保证任意两个城市连通。即这 nn 座城市构成一棵树。

每座城市都有一件宝物。宝物分为两种:钥匙和宝箱。在一座城市里,要么有一把钥匙,要么有一个宝箱。钥匙和宝箱有不同的颜色,颜色为 ii 的钥匙只能打开颜色为 ii 的宝箱,打开宝箱后可以获得一枚金币,同时这把钥匙会损坏。

由于某种特殊的原因,同一种的钥匙最多只有 5\bm{5} 把(同一种颜色的宝箱数量不限)。

现在小 R 规划了 mm 次旅行,第 ii 次旅行的起点为 sis_i,终点为 eie_i。小 R 从 sis_i 沿最短路径走到 eie_i。当他走到一座有钥匙的城市时,他可以将钥匙放入背包。当他走到一座有宝箱的城市时,如果他有相应颜色的钥匙,那么他就会打开这个宝箱并获得一个金币;如果他没有相应颜色的钥匙,那么他什么都不做(宝箱不能带走)。问每次旅行能获得多少枚金币。

注意:旅行相互独立,即一次旅行完之后所有的钥匙和宝箱都会恢复到初始状态。

输入格式

第一行两个正整数 n,mn, m,表示城市数量和旅行数量。

接下来 nn 行,每行两个正整数 ti,cit_i, c_iti=1t_i=1 表示第 ii 个城市里有一把钥匙,ti=2t_i=2 表示有一个宝箱。cic_i 表示第 ii 座城市里钥匙或宝箱的颜色。数据保证每种颜色的钥匙都不超过 55 把。

接下来 n1n - 1 行,每行两个正整数 ui,viu_i, v_i,表示有一条连接 uiu_iviv_i 的无向道路。

接下来 mm 行,每行两个正整数 si,eis_i, e_i 表示一次旅行的起点和终点。

输出格式

输出 mm 行,每行一个整数,表示第 ii 次旅行能获得的金币数量。

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

1
1
1

见附件中的 keys/keys2.in
见附件中的 keys/keys2.ans
见附件中的 keys/keys3.in
见附件中的 keys/keys3.ans

提示

【样例 #4】

见附件中的 keys/keys4.inkeys/keys4.ans

该组样例满足 n,m105n, m \le {10}^5 和特殊性质 A。

【数据范围】

对于 100%100 \% 的数据,1n5×1051 \le n \le 5 \times {10}^51m1061 \le m \le {10}^61ti21 \le t_i \le 21ci,ui,vi,si,ein1 \le c_i, u_i, v_i, s_i, e_i \le n,每种颜色的钥匙都不超过 55 把。

测试点编号 nn \le mm \le 特殊性质
11 100100
232 \sim 3 50005000
454 \sim 5 105{10}^5
686 \sim 8 5×1055 \times {10}^5 106{10}^6 A
9109 \sim 10

特殊性质 A:对于每种出现过的颜色,恰有一把钥匙和一个宝箱对应该颜色。

【提示】

输入输出数据较大,请使用较为快速的输入输出方式。