#PQJ479x6142. QOJ 479_6142

    ID: 2999 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2021 统一省选最短路径树上算法

QOJ 479_6142

全国青少年信息学奥林匹克竞赛 Day2(A 卷)宝石(gem) 宝石(gem) 【题目描述】 欧艾大陆上有n 座城市,城市从1 ∼n 编号,所有城市经由n −1 条无向道路互相 连通,即n 座城市与n −1 条道路构成了一棵树。 每座城市的集市上都会出售宝石,总共有m 种不同的宝石,用1 ∼m 编号。i 号 城市的集市出售的是第wi 种宝石,一种宝石可能会在多座城市的集市出售。 K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多c 颗宝石,其收集宝 石的顺序为:P1, P2, · · · , Pc。更具体地,收集器需要先放入第P1 种宝石,然后才能再放 入第P2 种宝石,之后再能放入第P3 种宝石,以此类推。其中P1, P2, · · · , Pc 互不相等。 K 神到达一个城市后,如果该城市的集市上出售的宝石种类和当前收集器中需要放 入的种类相同,则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中;否则他 只会路过该城市什么都不做。 现在K 神给了你q 次询问,每次给出起点si 与终点ti,他想知道如果从si 号城市 出发,沿最短路线走到ti 号城市后,他的收集器中最多能收集到几个宝石?(在每次询 问中,收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集) 【输入格式】 从文件gem.in 中读入数据。 第一行包含三个正整数n, m, c,分别表示城市数,宝石种类数,收集器的容量。 第二行包含c 个正整数Pi。数据保证1 ≤Pi ≤m 且这些数互不相等。 第三行包含n 个正整数wi,表示每个城市集市上出售的宝石种类。 接下来n −1 行,每行两个正整数ui, vi,表示一条连接ui 和vi 号城市的道路。 第n + 3 行包含一个正整数q 表示询问次数。 接下来q 行,每行两个正整数si,ti 表示该次询问的起点与终点。 【输出格式】 输出到文件gem.out 中。 按输入顺序输出q 行,每行一个整数表示询问的答案。 【样例1 输入】 1 7 3 3 2 2 3 1 3 2 1 3 3 2 1 3 4 1 2 第2 页 共7 页

全国青少年信息学奥林匹克竞赛 Day2(A 卷)宝石(gem) 5 2 3 6 1 4 7 4 5 8 4 6 9 6 7 10 5 11 3 5 12 1 3 13 7 3 14 5 7 15 7 5 【样例1 输出】 1 2 2 2 3 2 4 3 5 1 【样例2】 见选手目录下的gem/gem2.in 与gem/gem2.ans。 【样例3】 见选手目录下的gem/gem3.in 与gem/gem3.ans。 【数据范围】 对于所有测试数据:1 ≤n, q ≤2 × 105,1 ≤c ≤m ≤5 × 104,1 ≤wi ≤m。 每个测试点的具体限制见下表: 测试点编号 n, q ≤ 特殊限制 1 ∼2 10 无 3 ∼5 1000 6 ∼10 2 × 105 m ≤300 11 ∼14 ui = i,vi = i + 1 15 ∼20 无 第3 页 共7 页