#2426. 回忆
回忆
回忆
题目描述
NOI 2022 安徽省省队选拔 回忆(memory) 回忆(memory) 【题目背景】 生活在题面里的他们,是一群怪异的少年。 对城市中修建道路需满足的基本物理限制熟视无睹,沉迷于十万个城市、百万条道 路上的各种结构。 明明知道真正需要的数字庞大到无法计算,却偏要关心它模一个奇怪素数之后得到 的结果。 如此智力超群的他们,却总是在自己提出的诡异的问题下败下阵来,把它们一股脑 地丢给你们来做。 如今,他们长大了。他们学习到更普适的理论,习惯了更抽象的符号,不必再思考 如此古怪的问题。但他们不曾料到,你们却以这些“无用”的问题为驱动,于计算机学 科体系的一隅,开垦出了一片独属于OI 的新天地。 有一天,他们各自回忆起了少年时期提出的问题。 【题目描述】 少年时,他们提出了n 个问题,从1 到n 编号。一个问题总由一个更基础的问题 衍生而来,因此问题之间构成了一个树形的结构:1 号问题是最基本的问题,也就是树 的根节点,而其他问题都由其父亲节点对应的问题衍生而来。如果两个问题在树上相邻, 则称这两个问题.彼.此.相.关。 少年时期的他们一共做了m 次研究,第i 次的研究从提出较为基本的问题si 开 始,将它不断地修改、推广,最终提出问题ti。这些研究满足si̸ = ti 且si .必.定.是ti .的.祖.先。即使研究的问题完全相同,从不同的角度研究会有不同的结果,因此.可.能.存.在 i̸ = j, (si, ti) = (sj, tj) .的.情.形。 现在,他们正一轮轮地回忆着少年时提出的问题。在他们每一轮对问题的回忆中, 他们首先回忆到n 个问题中的任意一个。接下来,如果存在与当前回忆到的问题.彼.此.相 .关.且.在.这.轮.回.忆.中.没.有.被.回.忆.到的问题,那么他们可以将思绪从当前问题上切换到这些 问题中的.任.意.一.个,并回忆到这个新的问题。他们可以不断地切换思绪,也可以在回忆 到任何一个问题之后结束回忆。.每.一.轮.回.忆.是.独.立.的,.也.就.是.说.一.个.问.题.可.以.被.多.轮.回 .忆.回.忆.起。 如果在某一轮回忆中,他们.同.时回忆到了问题si 和问题ti,则称第i 次研究.被.想 .起。 为了更好地理解上述概念,考察以下例子:n = 5,问题1 与问题2, 3 相关,问题 3 与问题4, 5 相关。一轮可能的回忆是:从问题2 开始回忆,切换思绪到问题1 ,再 切换到问题3,最终切换到问题5 并结束回忆。如果m = 4,(s1, t1) = (1, 2), (s2, t2) = (1, 4), (s3, t3) = (s4, t4) = (3, 5),那么这轮回忆会让第1 次、第3 次和第4 次研究被想 起,而第2 次研究不会被想起。 第10 页 共15 页
NOI 2022 安徽省省队选拔 回忆(memory) 他们问你们的最后一个问题是:.如.果.每.轮.回.忆.的.起.点.以.及.思.绪.的.切.换.可.以.任.意.选 .择,.最.少.需.要.多.少.轮.回.忆.才.能.使.所.有.的.研.究.都.被.想.起。 【输入格式】 从文件memory.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行包含一个正整数T,表示数据组数。 对于每组测试数据,第一行包含两个正整数n, m,分别表示问题的个数和研究的个 数。 接下来n −1 行每行包含两个正整数ui, vi,表示问题ui 与问题vi 相关。 接下来m 行每行包含两个正整数si, ti,描述一次研究。 【输出格式】 输出到文件memory.out 中。 对于每组测试数据输出一行一个正整数,表示他们.最.少需要回忆的轮数使得m 次 研究均被想起。 【样例1 输入】 1 2 2 5 5 3 1 2 4 3 1 5 3 4 6 5 3 7 1 2 8 1 4 9 3 5 10 3 5 11 3 4 12 10 5 13 1 2 14 3 1 15 3 4 16 5 3 17 6 5 18 7 8 19 5 7 第11 页 共15 页
NOI 2022 安徽省省队选拔 回忆(memory) 20 7 9 21 9 10 22 1 2 23 3 5 24 5 6 25 7 8 26 9 10 【样例1 输出】 1 2 2 2 【样例1 解释】 样例中的第一组数据与题目描述所给的例子相同。一种可能的回忆方案为: • 第一轮回忆中,从问题2 开始,依次切换思绪到问题1, 3, 5。此时第1, 3, 4 次研 究被想起,但第2, 5 次没有。 • 第二轮回忆中,从问题4 开始,依次切换思绪到问题3, 1。此时第2, 5 次研究被 想起。 第二组数据符合特性A 的要求。一种可能的回忆方案为:第一次回忆依次回忆到 2, 1, 3, 5, 6,第二次回忆依次回忆到8, 7, 9, 10。 【样例2】 见选手目录下的memory/memory2.in 与memory/memory2.ans。 这组数据满足了测试点1 ∼4 的条件。 【样例3】 见选手目录下的memory/memory3.in 与memory/memory3.ans。 这组样例了特性A 的条件。且除了后3 组数据外,其余样例均满足n, m ≤1000。 除了后30 组数据外,其余样例均满足n, m ≤30。你也可以用这组样例完成对较小规模 数据的测试。 【样例4】 见选手目录下的memory/memory4.in 与memory/memory4.ans。 第12 页 共15 页
NOI 2022 安徽省省队选拔 回忆(memory) 这组样例满足了测试点24 ∼25 的条件。同第3 组样例,本样例满足:除了后3 组 数据外,其余样例均满足n, m ≤1000。除了后30 组数据外,其余样例均满足n, m ≤30。 你也可以用这组样例完成对较小规模数据的测试。 【样例5】 见选手目录下的memory/memory5.in 与memory/memory5.ans。 这组样例满足了特性B 的条件。 【样例6】 见选手目录下的memory/memory6.in 与memory/memory6.ans。 这组样例满足了特性C 的条件。 【子任务】 本题共25 个测试点。对于所有的测试点,1 ≤n, m ≤200000,1 ≤∑n, ∑m ≤ 500000,1 ≤ui, vi, si, ti ≤n,si̸ = ti。保证输入的(ui, vi) 构成一棵树,si 在以1 为根的 树上是ti 的祖先。 第13 页 共15 页
NOI 2022 安徽省省队选拔 回忆(memory) 测试点 规模限制 特性A 特性B 特性C 1 T ≤3000,n ≤50,m ≤15 且最多 有5 组数据满足m ≥10 No No No 2 3 4 5 n, m ≤100,∑n3, ∑m3 ≤3 · 107 Yes 6 7 No Yes 8 No Yes 9 No 10 n, m ≤1000,∑n2, ∑m2 ≤3 · 107 Yes 11 12 No Yes 13 No Yes 14 No 15 16 17 n, m ≤2 · 105,∑n, ∑m ≤5 · 105 Yes 18 19 No Yes 20 21 Yes No 22 23 24 No 25 特性A:保证n 为偶数,且树的结构为:对于任意正整数1 ≤i ≤⌊n 2⌋,2i 的父亲 为2i −1;若i ≥2,则2i −1 的父亲为2i −3。 特性B:保证对于所有的正整数1 ≤i ≤m,si 为ti 的父亲。 特性C:保证对于所有的正整数1 ≤i ≤m,si = 1。 请注意,.测.试.点.的.难.度.与.编.号.并.没.有.直.接.关.系。 【评分方式】 对于每一组测试点,如果你的输出格式正确,且每一组数据输出的答案正确,那么 你会获得4 分。 第14 页 共15 页
NOI 2022 安徽省省队选拔 回忆(memory) 否则,如果你的输出格式正确,且对于每一组数据,你输出的答案.与.正.确.答.案.相.等 .或.者.比.正.确.答.案.大1,那么你将在此测试点上获得3 分。 【提示】 请注意,为了取得部分分,你必须保证输出格式正确,即:输出恰好有m 行,且每 行是一个正整数。 此外,如果某组测试数据中你输出的结果比答案小1 而不是大1,那么你.不.能在该 测试点获得3 分。 本题部分测试点读入量较大。为了优化程序的总运行时间,我们建议你采用较为快 速的读入方式。 第15 页 共15 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
5 5
1 2
3 1
3 4
5 3
1 2
1 4
3 5
3 5
3 4
10 5
1 2
3 1
3 4
5 3
6 5
7 8
5 7
7 9
9 10
1 2
3 5
5 6
7 8
9 10
2
2