P15654 [省选联考 2026] 工业系统 / industry

最近，小绯在自家花园里考古的时候，发现了一些看上去很古老的工业设备。好奇心旺盛的她心血来潮，决定测试一下这些设备的性能。 于是，她找来了一些传送带，照着花园里一棵桃树的样子，把这些设备连接了起来，形成了一套工业系统。 至于具体的测试方法，自然是由你回答小绯的询问。相信你不会拒绝的！

给定一套包含 $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} = \varnothing$。 为了便于比较产物品质的优劣，可以定义产物的大小关系如下：指定设备 $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 解释】 - 以设备 $1$ 为根时， - 设备 $3$ 为叶设备，因此 $a_{1,3} = \varnothing$； - 设备 $2$ 的所有后代设备为设备 $3$，因此 $a_{1,2} = \{\varnothing\}$； - 设备 $1$ 的所有后代设备为设备 $2, 3$，因此 $a_{1,1} = \{\varnothing, \{\varnothing\}\}$； - 因此 $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} = \varnothing$； - 设备 $2$ 的所有后代设备为设备 $1, 3$，因此 $a_{2,2} = \{\varnothing, \varnothing\}$； - 因此 $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} = \varnothing$； - 设备 $2$ 的所有后代设备为设备 $1$，因此 $a_{3,2} = \{\varnothing\}$； - 设备 $3$ 的所有后代设备为设备 $1, 2$，因此 $a_{3,3} = \{\varnothing, \{\varnothing\}\}$； - 因此 $a_{3,3} > a_{3,2} > a_{3,1}$，即 $f(3,3) = 1$，$f(3,2) = 2$，$f(3,1) = 3$。 ### 【样例 2】 见选手目录下的 `industry/industry2.in` 与 `industry/industry2.ans`。 ### 【样例 2 解释】 - 以设备 $1$ 为根时，$a_{1,2} = a_{1,6} = a_{1,5} = \varnothing$，$a_{1,4} = \{\varnothing\}$，$a_{1,3} = \{\varnothing, \varnothing, \{\varnothing\}\}$，$a_{1,1} = \{\varnothing, \varnothing, \varnothing, \{\varnothing\}, \{\varnothing, \varnothing, \{\varnothing\}\}\}$，因此 $a_{1,1} > a_{1,3} > a_{1,4} > a_{1,2} = a_{1,5} = a_{1,6}$。 - 以设备 $2$ 为根时，$a_{2,2} > a_{2,4} > a_{2,3} > a_{2,1} > a_{2,5} = a_{2,6}$。 - 以设备 $3$ 为根时，$a_{3,3} > a_{3,1} = a_{3,4} > a_{3,2} = a_{3,5} = a_{3,6}$。 - 以设备 $4$ 为根时，$a_{4,4} > a_{4,3} > a_{4,1} > a_{4,2} = a_{4,5} = a_{4,6}$。 - 以设备 $5$ 为根时，$a_{5,5} > a_{5,1} > a_{5,3} > a_{5,4} > a_{5,2} = a_{5,6}$； - 以设备 $6$ 为根时，$a_{6,6} > a_{6,3} > a_{6,1} = a_{6,4} > a_{6,2} = a_{6,5}$。 ### 【样例 3】 见选手目录下的 `industry/industry3.in` 与 `industry/industry3.ans`。 ### 【样例 4】 见选手目录下的 `industry/industry4.in` 与 `industry/industry4.ans`。 该样例满足 $o_x = o_y = 0$。 ### 【样例 5】 见选手目录下的 `industry/industry5.in` 与 `industry/industry5.ans`。 该样例满足 $o_x = 0$ 且 $o_y = 1$。 ### 【样例 6】 见选手目录下的 `industry/industry6.in` 与 `industry/industry6.ans`。 该样例满足 $o_x = 1$ 且 $o_y = 0$。 ### 【样例 7】 见选手目录下的 `industry/industry7.in` 与 `industry/industry7.ans`。 该样例满足 $o_x = o_y = 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$ 的约束条件。 ### 【样例 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\sim 11$ 的约束条件。 ### 【样例 14】 见选手目录下的 `industry/industry14.in` 与 `industry/industry14.ans`。 该样例满足测试点 $12\sim 14$ 的约束条件。 ### 【样例 15】 见选手目录下的 `industry/industry15.in` 与 `industry/industry15.ans`。 该样例满足测试点 $15\sim 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\sim 24$ 的约束条件。 ### 【样例 19】 见选手目录下的 `industry/industry19.in` 与 `industry/industry19.ans`。 该样例满足测试点 $25$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $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\}$。 ::cute-table{tuack} | 测试点编号 | $n, m \le$ | $o_x$ | $o_y$ | $r$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $10^5$ | $\in \{0,1\}$ | $\in \{0,1\}$ | $\le n$ | A | | $2$ | ^ | ^ | ^ | $= 1$ | B | | $3, 4$ | ^ | $= 0$ | $= 0$ | $= 2$ | ^ | | $5, 6$ | $10$ | ^ | ^ | $\le n$ | ^ | | $7, 8$ | $2\,000$ | ^ | ^ | ^ | ^ | | $9 \sim 11$ | $10^5$ | ^ | ^ | ^ | ^ | | $12 \sim 14$ | ^ | ^ | $= 1$ | ^ | 无 | | $15 \sim 17$ | ^ | $= 1$ | $= 0$ | ^ | ^ | | $18, 19$ | ^ | ^ | $= 1$ | ^ | B | | $20, 21$ | $5 \times 10^4$ | ^ | ^ | ^ | 无 | | $22 \sim 24$ | $10^5$ | ^ | ^ | ^ | ^ | | $25$ | ^ | $\in \{0,1\}$ | $\in \{0,1\}$ | ^ | ^ | 特殊性质 A：存在 $1 \le x \le n$ 满足对于所有 $1 \le i \le n - 1$，均有 $u_i = x$ 或 $v_i = x$。 特殊性质 B：所有设备构成的无根树在 $n$ 个点的有标号无根树中**等概率随机**生成。