#PQJ928x4046. QOJ 928_4046

    ID: 3066 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:AHOI 2022背包树上算法

QOJ 928_4046

NOI 2022 安徽省省队选拔 钥匙(keys) 钥匙(keys) 【题目描述】 有n 座城市,编号为1, 2, . . . , n。这些城市由n −1 条无向道路相连,每条无向道 路连接两座城市,保证任意两个城市连通。即这n 座城市构成一棵树。 每座城市都有一件宝物。宝物分为两种:钥匙和宝箱。在一座城市里,要么有一把 钥匙,要么有一个宝箱。钥匙和宝箱有不同的颜色,颜色为i 的钥匙只能打开颜色为i 的宝箱,打开宝箱后可以获得一枚金币,同时这把钥匙会损坏。 .由.于.某.种.特.殊.的.原.因,.同.一.种.的.钥.匙.最.多.只.有5 .把(.同.一.种.颜.色.的.宝.箱.数.量.不.限)。 现在小R 规划了m 次旅行,第i 次旅行的起点为si,终点为ei。小R 从si 沿最 短路径走到ei。当他走到一座有钥匙的城市时,他可以将钥匙放入背包。当他走到一座 有宝箱的城市时,如果他有相应颜色的钥匙,那么他就会打开这个宝箱并获得一个金币; 如果他没有相应颜色的钥匙,那么他什么都不做(宝箱不能带走)。问每次旅行能获得 多少枚金币。 .注.意:.旅.行.相.互.独.立,.即.一.次.旅.行.完.之.后.所.有.的.钥.匙.和.宝.箱.都.会.恢.复.到.初.始.状.态。 【输入格式】 从文件keys.in 中读入数据。 第一行两个正整数n, m,表示城市数量和旅行数量。 接下来n 行,每行两个正整数ti, ci,ti = 1 表示第i 个城市里有一把钥匙,ti = 2 表示有一个宝箱。ci 表示第i 座城市里钥匙或宝箱的颜色。数据保证每种颜色的钥匙都 不超过5 把。 接下来n −1 行,每行两个正整数ui, vi,表示有一条连接ui 和vi 的无向道路。 接下来m 行,每行两个正整数si, ei 表示一次旅行的起点和终点。 【输出格式】 输出到文件keys.out 中。 输出m 行,每行一个整数,表示第i 次旅行能获得的金币数量。 【样例1 输入】 1 5 3 2 1 2 3 2 2 4 1 3 5 2 3 第5 页 共15 页

NOI 2022 安徽省省队选拔 钥匙(keys) 6 2 2 7 1 2 8 1 3 9 3 4 10 3 5 11 2 4 12 2 5 13 4 2 【样例1 输出】 1 1 2 1 3 1 【样例2】 见选手目录下的keys/keys2.in 与keys/keys2.ans。 【样例3】 见选手目录下的keys/keys3.in 与keys/keys3.ans。 【样例4】 见选手目录下的keys/keys4.in 与keys/keys4.ans。 该组样例满足n, m ≤105 和特殊性质A。 【子任务】 对于100% 的数据,1 ≤n ≤5×105,1 ≤m ≤106,1 ≤ti ≤2,1 ≤ci, ui, vi, si, ei ≤n, 每种颜色的钥匙都不超过5 把。 测试点编号 n ≤ m ≤ 特殊性质 1 100 100 无 2 ∼3 5000 5000 4 ∼5 105 105 6 ∼8 5 × 105 106 A 9 ∼10 无 第6 页 共15 页

NOI 2022 安徽省省队选拔 钥匙(keys) 特殊性质A:对于每种出现过的颜色,恰有一把钥匙和一个宝箱对应该颜色。 【提示】 输入输出数据较大,请使用较为快速的输入输出方式。 第7 页 共15 页