#PQJ3494x17306. QOJ 3494_17306

    ID: 2933 传统题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十七省联合省选2026树上算法排序计算几何

QOJ 3494_17306

2026 联合省选 第二试工业系统(industry) 工业系统(industry) 【题目背景】 最近,小绯在自家花园里考古的时候,发现了一些看上去很古老的工业设备。好奇 心旺盛的她心血来潮,决定测试一下这些设备的性能。 于是,她找来了一些传送带,照着花园里一棵桃树的样子,把这些设备连接了起来, 形成了一套工业系统。 至于具体的测试方法,自然是由你回答小绯的询问。相信你不会拒绝的! 【题目描述】 给定一套包含n 台设备的工业系统,设备的编号为1 ∼n。这些设备由n −1 条方 向可变的有向传送带相连,构成一棵无根树。 在使用这套系统时,首先需要指定一台设备x (1 ≤x ≤n) 作为最终设备,然后会 将所有传送带的方向设置为指向该设备的方向。形式化地,设备x 被指定为树根,所有 传送带的方向设置为指向根的方向,形成一棵内向有根树。确定所有传送带的方向后, 所有产物将会沿着传送带的方向运输。 每台设备会接收其.所.有.后.代设备的产物作为输入产物,然后生产出一种新的产物, 并将其沿传送带输出至.所.有.祖.先设备。形式化地,设设备y (1 ≤y ≤n) 的产物为 ax,y,其子树内的除该设备外的所有设备分别为z1, . . . , zk,则其产物可被表示为.可.重 .集ax,y = {ax,z1, . . . , ax,zk}。特别地,若设备y 为叶设备,即设备y 没有后代设备,则 ax,y = ∅。 为了便于比较产物品质的优劣,可以.递.归.地定义产物的大小关系如下:指定设备 x (1 ≤x ≤n) 作为最终设备时,对于设备y, z (1 ≤y, z ≤n) 的产物ax,y, ax,z,将 ax,y, ax,z 中的所有元素(即设备y, z 的所有输入产物)分别.从.大.到.小.排.序后,得到的两 个序列的.字.典.序大小关系即为ax,y, ax,z 的大小关系。形式化地,设ax,y = {b1, b2, . . . , bp}, ax,z = {c1, c2, . . . , cq},其中b1 ≥b2 ≥· · · ≥bp,c1 ≥c2 ≥· · · ≥cq,则有: • ax,y > ax,z 当且仅当满足以下两个条件之一: – 存在正整数i ∈[1, min(p, q)] 满足bi > ci,且对于所有1 ≤j < i 均有bj = cj; – 对于所有1 ≤i ≤min(p, q),均有bi = ci,且p > q; • ax,y = ax,z 当且仅当p = q 且对于所有1 ≤i ≤p,均有bi = ci。 在定义产物的大小关系后,可以定义产物的排名。具体地,定义f(x, y) (1 ≤x, y ≤n) 表示:指定设备x 作为最终设备时,设备y 的产物ax,y 在所有n 种产物中的排名。形 式化地, f(x, y) = 1 + n ! z=1 [ax,z > ax,y]. 为了全面地分析各个设备在该工业系统中的作用,你需要回答m 次询问。一次询 问的形式如下: 第11 页 共16 页

2026 联合省选 第二试工业系统(industry) • 给定五个参数s, t, ox, oy, r; • 定义 X =    {s}, ox = 0, ch(s, t), ox = 1, Y =    {t}, oy = 0, ch(s, t), oy = 1, • 其中ch(s, t) 表示设备s 到设备t 的简单路径上的所有设备构成的集合; • 求有多少对(x, y) 满足x ∈X,y ∈Y 且f(x, y) ≤r。 【输入格式】 从文件industry.in 中读入数据。 输入的第一行包含一个非负整数c,表示测试点编号。c = 0 表示该测试点为样例。 输入的第二行包含一个正整数n,表示该工业系统包含的设备数。 输入的第i + 2 (1 ≤i ≤n −1) 行包含两个正整数ui, vi,表示第i 条传送带连接的 两台设备的编号。 输入的第n + 2 行包含一个正整数m,表示询问次数。 输入的第i + n + 2 (1 ≤i ≤m) 行包含五个非负整数s, t, ox, oy, r,表示第i 次询问 给定的参数。 【输出格式】 输出到文件industry.out 中。 输出m 行,其中第i (1 ≤i ≤m) 行包含一个非负整数,表示第i 次询问的答案。 【样例1 输入】 1 0 2 3 3 1 2 4 2 3 5 6 6 1 2 0 0 2 7 1 3 0 0 2 8 2 3 0 0 2 9 2 1 0 0 2 10 3 1 0 0 2 11 3 2 0 0 2 第12 页 共16 页

2026 联合省选 第二试工业系统(industry) 【样例1 输出】 1 1 2 0 3 1 4 1 5 0 6 1 【样例1 解释】 • 以设备1 为根时, – 设备3 为叶设备,因此a1,3 = ∅; – 设备2 的所有后代设备为设备3,因此a1,2 = {∅}; – 设备1 的所有后代设备为设备2, 3,因此a1,1 = {{∅}, ∅}; – 因此a1,1 > a1,2 > a1,3,即f(1, 1) = 1,f(1, 2) = 2,f(1, 3) = 3。 • 以设备2 为根时, – 设备1, 3 为叶设备,因此a2,1 = a2,3 = ∅; – 设备2 的所有后代设备为设备1, 3,因此a2,2 = {∅, ∅}; – 因此a2,2 > a2,1 = a2,3,即f(2, 2) = 1,f(2, 1) = f(2, 3) = 2。 • 以设备3 为根时, – 设备1 为叶设备,因此a3,1 = ∅; – 设备2 的所有后代设备为设备1,因此a3,2 = {∅}; – 设备3 的所有后代设备为设备1, 2,因此a3,3 = {{∅}, ∅}; – 因此a3,3 > a3,2 > a3,1,即f(3, 3) = 1,f(3, 2) = 2,f(3, 1) = 3。 【样例2】 见选手目录下的industry/industry2.in 与industry/industry2.ans。 【样例2 解释】 • 以设备1 为根时,a1,2 = a1,6 = a1,5 = ∅,a1,4 = {∅},a1,3 = {{∅}, ∅, ∅}, a1,1 = {{{∅}, ∅, ∅}, {∅}, ∅, ∅, ∅},因此a1,1 > a1,3 > a1,4 > a1,2 = a1,5 = a1,6。 • 以设备2 为根时,a2,2 > a2,4 > a2,3 > a2,1 > a2,5 = a2,6; • 以设备3 为根时,a3,3 > a3,1 = a3,4 > a3,2 = a3,5 = a3,6; • 以设备4 为根时,a4,4 > a4,3 > a4,1 > a4,2 = a4,5 = a4,6; 第13 页 共16 页

2026 联合省选 第二试工业系统(industry) • 以设备5 为根时,a5,5 > a5,1 > a5,3 > a5,4 > a5,2 = a5,6; • 以设备6 为根时,a6,6 > a6,3 > a6,1 = a6,4 > a6,2 = a6,5。 【样例3】 见选手目录下的industry/industry3.in 与industry/industry3.ans。 【样例4】 见选手目录下的industry/industry4.in 与industry/industry4.ans。 该样例满足ox = oy = 0。 【样例5】 见选手目录下的industry/industry5.in 与industry/industry5.ans。 该样例满足ox = 0 且oy = 1。 【样例6】 见选手目录下的industry/industry6.in 与industry/industry6.ans。 该样例满足ox = 1 且oy = 0。 【样例7】 见选手目录下的industry/industry7.in 与industry/industry7.ans。 该样例满足ox = oy = 1。 【样例8】 见选手目录下的industry/industry8.in 与industry/industry8.ans。 该样例满足测试点1 的约束条件。 【样例9】 见选手目录下的industry/industry9.in 与industry/industry9.ans。 该样例满足测试点2 的约束条件。 【样例10】 见选手目录下的industry/industry10.in 与industry/industry10.ans。 该样例满足测试点3, 4 的约束条件。 第14 页 共16 页

2026 联合省选 第二试工业系统(industry) 【样例11】 见选手目录下的industry/industry11.in 与industry/industry11.ans。 该样例满足测试点5, 6 的约束条件。 【样例12】 见选手目录下的industry/industry12.in 与industry/industry12.ans。 该样例满足测试点7, 8 的约束条件。 【样例13】 见选手目录下的industry/industry13.in 与industry/industry13.ans。 该样例满足测试点9 ∼11 的约束条件。 【样例14】 见选手目录下的industry/industry14.in 与industry/industry14.ans。 该样例满足测试点12 ∼14 的约束条件。 【样例15】 见选手目录下的industry/industry15.in 与industry/industry15.ans。 该样例满足测试点15 ∼17 的约束条件。 【样例16】 见选手目录下的industry/industry16.in 与industry/industry16.ans。 该样例满足测试点18, 19 的约束条件。 【样例17】 见选手目录下的industry/industry17.in 与industry/industry17.ans。 该样例满足测试点20, 21 的约束条件。 【样例18】 见选手目录下的industry/industry18.in 与industry/industry18.ans。 该样例满足测试点22 ∼24 的约束条件。 第15 页 共16 页

2026 联合省选 第二试工业系统(industry) 【样例19】 见选手目录下的industry/industry19.in 与industry/industry19.ans。 该样例满足测试点25 的约束条件。 【数据范围】 对于所有测试数据,均有: • 2 ≤n ≤105; • 对于所有1 ≤i ≤n −1,均有1 ≤ui, vi ≤n,且(u1, v1), . . . , (un−1, vn−1) 构成一 棵树; • 1 ≤m ≤105; • 1 ≤s, t, r ≤n,ox, oy ∈{0, 1}。 测试点编号 n, m ≤ ox oy r 特殊性质 1 105 ∈{0, 1} ∈{0, 1} ≤n A 2 = 1 B 3, 4 = 0 = 0 = 2 5, 6 10 ≤n 7, 8 2,000 9 ∼11 105 12 ∼14 = 1 无 15 ∼17 = 1 = 0 18, 19 = 1 B 20, 21 5 ×104 无 22 ∼24 105 25 ∈{0, 1} ∈{0, 1} 特殊性质A:存在1 ≤x ≤n 满足对于所有1 ≤i ≤n −1,均有ui = x 或vi = x。 特殊性质B:所有设备构成的无根树在n 个点的有标号无根树中.等.概.率.随.机生成。 第16 页 共16 页