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

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

1
0
1
1
0
1

说明/提示

【样例 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\}$		$\le n$	A
$2$	^	^		$= 1$	B
$3, 4$		$= 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\}$

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

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

附加文件下载

industry.zip