4357. [省选联考 2026] 工业系统

【题目背景】

最近，小绯在自家花园里考古的时候，发现了一些看上去很古老的工业设备。好奇心旺盛的她心血来潮，决定测试一下这些设备的性能。

于是，她找来了一些传送带，照着花园里一棵桃树的样子，把这些设备连接了起来，形成了一套工业系统。

至于具体的测试方法，自然是由你回答小绯的询问。相信你不会拒绝的！

【题目描述】

给定一套包含 $n$ 台设备的工业系统，设备的编号为 $1 \sim n$。这些设备由 $n-1$ 条方向可变的有向传送带相连，构成一棵无根树。

在使用这套系统时，首先需要指定一台设备 $x$（$1 \le x \le n$）作为最终设备，然后会将所有传送带的方向设置为指向该设备的方向。形式化地，设备 $x$ 被指定为树根，所有传送带的方向设置为指向根的方向，形成一棵内向有根树。确定所有传送带的方向后，所有产物将会沿着传送带的方向运输。

每台设备会接收其所有后代设备的产物作为输入产物，然后生产出一种新的产物，并将其沿传送带输出至所有祖先设备。形式化地，设设备 $y$（$1 \le y \le n$）的产物为 $a_{x,y}$，其子树内的除该设备外的所有设备分别为 $z_1, \dots, z_k$，则其产物可被表示为可重集 $a_{x,y} = \{a_{x,z_1}, \dots, a_{x,z_k}\}$。特别地，若设备 $y$ 为叶设备，即设备 $y$ 没有后代设备，则 $a_{x,y} = ∅$。

为了便于比较产物品质的优劣，可以定义产物的大小关系如下：指定设备 $x$（$1 \le x \le n$）作为最终设备时，对于设备 $y, z$（$1 \le y, z \le n$）的产物 $a_{x,y}, a_{x,z}$，将 $a_{x,y}, a_{x,z}$ 中的所有元素（即设备 $y, z$ 的所有输入产物）分别从大到小排序后，得到的两个序列的字典序大小关系即为 $a_{x,y}, a_{x,z}$ 的大小关系。形式化地，设 $a_{x,y} = \{b_1, b_2, \dots, b_p\}$，$a_{x,z} = \{c_1, c_2, \dots, c_q\}$，其中 $b_1 \ge b_2 \ge \dots \ge b_p$，$c_1 \ge c_2 \ge \dots \ge c_q$，则有：

$a_{x,y} > a_{x,z}$ 当且仅当满足以下两个条件之一：

 存在正整数 $i \in [1, \min(p, q)]$ 满足 $b_i > c_i$，且对于所有 $1 \le j < i$ 均有 $b_j = c_j$；

 对于所有 $1 \le i \le \min(p, q)$，均有 $b_i = c_i$，且 $p > q$；

$a_{x,y} = a_{x,z}$ 当且仅当 $p = q$ 且对于所有 $1 \le i \le p$，均有 $b_i = c_i$。

在定义产物的大小关系后，可以定义产物的排名。具体地，定义 $f(x, y)$（$1 \le x, y \le n$）表示：指定设备 $x$ 作为最终设备时，设备 $y$ 的产物 $a_{x,y}$ 在所有 $n$ 种产物中的排名。形式化地，

$$f(x, y) = 1 + \sum_{z=1}^{n} [a_{x,z} > a_{x,y}].$$

为了全面地分析各个设备在该工业系统中的作用，你需要回答 $m$ 次询问。一次询问的形式如下：

给定五个参数 $s, t, o_x, o_y, r$；

定义

 $$X = \begin{cases}\{s\}, & o_x = 0, \\ \text{ch}(s,t), & o_x = 1,\end{cases} \quad Y = \begin{cases} \{t\}, & o_y = 0, \\ \text{ch}(s,t), & o_y = 1,\end{cases}$$

其中 $\text{ch}(s,t)$ 表示设备 $s$ 到设备 $t$ 的简单路径上的所有设备构成的集合；

求有多少对 $(x, y)$ 满足 $x \in X$，$y \in Y$ 且 $f(x, y) \le r$。

【输入格式】

输入的第一行包含一个非负整数 $c$，表示测试点编号。$c = 0$ 表示该测试点为样例。

输入的第二行包含一个正整数 $n$，表示该工业系统包含的设备数。

输入的第 $i+2$（$1 \le i \le n-1$）行包含两个正整数 $u_i, v_i$，表示第 $i$ 条传送带连接的两台设备的编号。

输入的第 $n+2$ 行包含一个正整数 $m$，表示询问次数。

输入的第 $i+n+2$（$1 \le i \le m$）行包含五个非负整数 $s, t, o_x, o_y, r$，表示第 $i$ 次询问给定的参数。

【输出格式】

输出 $m$ 行，其中第 $i$（$1 \le i \le m$）行包含一个非负整数，表示第 $i$ 次询问的答案。

【样例 1 输入】

0
3
1 2
2 3
6
1 2 0 0 2
1 3 0 0 2
2 3 0 0 2
2 1 0 0 2
3 1 0 0 2
3 2 0 0 2

【样例输出】

1
0
1
1
0
1

【样例 1 说明】

以设备 $1$ 为根时，

 设备 $3$ 为叶设备，因此 $a_{1,3} = ∅$；

 设备 $2$ 的所有后代设备为设备 $3$，因此 $a_{1,2} = \{∅\}$；

 设备 $1$ 的所有后代设备为设备 $2, 3$，因此 $a_{1,1} = \{∅, \{∅\}\}$；

 因此 $a_{1,1} > a_{1,2} > a_{1,3}$，即 $f(1,1) = 1$，$f(1,2) = 2$，$f(1,3) = 3$。

以设备 $2$ 为根时，

 设备 $1, 3$ 为叶设备，因此 $a_{2,1} = a_{2,3} = ∅$；

 设备 $2$ 的所有后代设备为设备 $1, 3$，因此 $a_{2,2} = \{∅, ∅\}$；

 因此 $a_{2,2} > a_{2,1} = a_{2,3}$，即 $f(2,2) = 1$，$f(2,1) = f(2,3) = 2$。

以设备 $3$ 为根时，

 设备 $1$ 为叶设备，因此 $a_{3,1} = ∅$；

 设备 $2$ 的所有后代设备为设备 $1$，因此 $a_{3,2} = \{∅\}$；

 设备 $3$ 的所有后代设备为设备 $1, 2$，因此 $a_{3,3} = \{∅, \{∅\}\}$；

 因此 $a_{3,3} > a_{3,2} > a_{3,1}$，即 $f(3,3) = 1$，$f(3,2) = 2$，$f(3,1) = 3$。

【样例 2】

【样例 2 解释】

【数据规模与约定】

对于所有测试数据，均有：

$2 \le n \le 10^5$；

对于所有 $1 \le i \le n-1$，均有 $1 \le u_i, v_i \le n$，且 $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ 构成一棵树；

$1 \le m \le 10^5$；

$1 \le s, t, r \le n$，$o_x, o_y \in \{0,1\}$。

特殊性质 A：存在 $1 \le x \le n$ 满足对于所有 $1 \le i \le n 1$，均有 $u_i = x$ 或 $v_i = x$。

特殊性质 B：所有设备构成的无根树在 $n$ 个点的有标号无根树中等概率随机生成。

【来源】

[省选联考 2026] D2T3

样例下载