Background

Recently, while doing archaeology in her own garden, Xiaofei found some industrial devices that looked very old. Out of curiosity, she suddenly decided to test the performance of these devices.

So she found some conveyor belts and, following the shape of a peach tree in the garden, connected these devices together to form an industrial system.

As for the specific testing method, you will naturally answer Xiaofei’s questions. Surely you will not refuse.

Problem Description

You are given an industrial system containing $n$ devices, numbered $1 \sim n$. These devices are connected by $n-1$ directed conveyor belts whose directions can be changed, forming an unrooted tree.

When using this system, you first need to choose a device $x$ ($1 \le x \le n$) as the final device, and then set the direction of every conveyor belt to point toward that device. Formally, device $x$ is chosen as the root of the tree, and all conveyor belts are directed toward the root, forming an inward rooted tree. After the directions are fixed, all products will be transported along the conveyor directions.

Each device takes the products of all its descendants as input products, then produces a new product, and outputs it along the conveyor belt to all its ancestors. Formally, let the product of device $y$ ($1 \le y \le n$) be $a_{x,y}$. Let all devices in the subtree of $y$ except itself be $z_1, \dots, z_k$. Then its product can be represented as the multiset $a_{x,y} = \{a_{x,z_1}, \dots, a_{x,z_k}\}$. In particular, if device $y$ is a leaf device, i.e. $y$ has no descendants, then $a_{x,y} = \varnothing$.

To compare product quality, define the order between products as follows. When device $x$ ($1 \le x \le n$) is chosen as the final device, for products $a_{x,y}, a_{x,z}$ of devices $y, z$ ($1 \le y, z \le n$), sort all elements in $a_{x,y}$ and $a_{x,z}$ (i.e. all input products of devices $y, z$) from large to small, obtaining two sequences. The lexicographic order of these two sequences is defined as the order between $a_{x,y}$ and $a_{x,z}$. Formally, let $a_{x,y} = \{b_1, b_2, \dots, b_p\}$, $a_{x,z} = \{c_1, c_2, \dots, c_q\}$, where $b_1 \ge b_2 \ge \dots \ge b_p$ and $c_1 \ge c_2 \ge \dots \ge c_q$. Then:

• $a_{x,y} > a_{x,z}$ if and only if one of the following holds:
  • There exists a positive integer $i \in [1, \min(p, q)]$ such that $b_i > c_i$, and for all $1 \le j < i$ we have $b_j = c_j$.
  • For all $1 \le i \le \min(p, q)$ we have $b_i = c_i$, and $p > q$.
• $a_{x,y} = a_{x,z}$ if and only if $p = q$ and for all $1 \le i \le p$ we have $b_i = c_i$.

After defining the order, we define the rank of a product. Specifically, define $f(x, y)$ ($1 \le x, y \le n$) as: when device $x$ is chosen as the final device, the rank of device $y$’s product $a_{x,y}$ among all $n$ products. Formally,

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

To fully analyze the role of each device in this industrial system, you need to answer $m$ queries. Each query is:

• Given five parameters $s, t, o_x, o_y, r$.
• Define$$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}$$
• where $\text{ch}(s,t)$ denotes the set of all devices on the simple path from device $s$ to device $t$.
• Find how many pairs $(x, y)$ satisfy $x \in X$, $y \in Y$, and $f(x, y) \le r$.

Input Format

The first line contains a non-negative integer $c$, the test point ID. $c = 0$ means this test point is the sample.

The second line contains a positive integer $n$, the number of devices in the industrial system.

The $(i+2)$-th line ($1 \le i \le n-1$) contains two positive integers $u_i, v_i$, meaning the $i$-th conveyor belt connects devices $u_i$ and $v_i$.

The $(n+2)$-th line contains a positive integer $m$, the number of queries.

The $(i+n+2)$-th line ($1 \le i \le m$) contains five non-negative integers $s, t, o_x, o_y, r$, the parameters of the $i$-th query.

Output Format

Output $m$ lines. The $i$-th line ($1 \le i \le m$) contains a non-negative integer, the answer to the $i$-th query.

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

Hint

Sample 1 Explanation.

• When device $1$ is the root:
  • Device $3$ is a leaf device, so $a_{1,3} = \varnothing$.
  • The descendants of device $2$ are device $3$, so $a_{1,2} = \{\varnothing\}$.
  • The descendants of device $1$ are devices $2, 3$, so $a_{1,1} = \{\varnothing, \{\varnothing\}\}$.
  • Therefore $a_{1,1} > a_{1,2} > a_{1,3}$, i.e. $f(1,1) = 1$, $f(1,2) = 2$, $f(1,3) = 3$.
• When device $2$ is the root:
  • Devices $1, 3$ are leaf devices, so $a_{2,1} = a_{2,3} = \varnothing$.
  • The descendants of device $2$ are devices $1, 3$, so $a_{2,2} = \{\varnothing, \varnothing\}$.
  • Therefore $a_{2,2} > a_{2,1} = a_{2,3}$, i.e. $f(2,2) = 1$, $f(2,1) = f(2,3) = 2$.
• When device $3$ is the root:
  • Device $1$ is a leaf device, so $a_{3,1} = \varnothing$.
  • The descendants of device $2$ are device $1$, so $a_{3,2} = \{\varnothing\}$.
  • The descendants of device $3$ are devices $1, 2$, so $a_{3,3} = \{\varnothing, \{\varnothing\}\}$.
  • Therefore $a_{3,3} > a_{3,2} > a_{3,1}$, i.e. $f(3,3) = 1$, $f(3,2) = 2$, $f(3,1) = 3$.

Sample 2.

See industry/industry2.in and industry/industry2.ans in the contestant directory.

Sample 2 Explanation.

• When device $1$ is the root, $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\}\}\}$, so $a_{1,1} > a_{1,3} > a_{1,4} > a_{1,2} = a_{1,5} = a_{1,6}$.
• When device $2$ is the root, $a_{2,2} > a_{2,4} > a_{2,3} > a_{2,1} > a_{2,5} = a_{2,6}$.
• When device $3$ is the root, $a_{3,3} > a_{3,1} = a_{3,4} > a_{3,2} = a_{3,5} = a_{3,6}$.
• When device $4$ is the root, $a_{4,4} > a_{4,3} > a_{4,1} > a_{4,2} = a_{4,5} = a_{4,6}$.
• When device $5$ is the root, $a_{5,5} > a_{5,1} > a_{5,3} > a_{5,4} > a_{5,2} = a_{5,6}$.
• When device $6$ is the root, $a_{6,6} > a_{6,3} > a_{6,1} = a_{6,4} > a_{6,2} = a_{6,5}$.

Sample 3.

See industry/industry3.in and industry/industry3.ans in the contestant directory.

Sample 4.

See industry/industry4.in and industry/industry4.ans in the contestant directory.

This sample satisfies $o_x = o_y = 0$.

Sample 5.

See industry/industry5.in and industry/industry5.ans in the contestant directory.

This sample satisfies $o_x = 0$ and $o_y = 1$.

Sample 6.

See industry/industry6.in and industry/industry6.ans in the contestant directory.

This sample satisfies $o_x = 1$ and $o_y = 0$.

Sample 7.

See industry/industry7.in and industry/industry7.ans in the contestant directory.

This sample satisfies $o_x = o_y = 1$.

Sample 8.

See industry/industry8.in and industry/industry8.ans in the contestant directory.

This sample satisfies the constraints of test point $1$.

Sample 9.

See industry/industry9.in and industry/industry9.ans in the contestant directory.

This sample satisfies the constraints of test point $2$.

Sample 10.

See industry/industry10.in and industry/industry10.ans in the contestant directory.

This sample satisfies the constraints of test points $3,4$.

Sample 11.

See industry/industry11.in and industry/industry11.ans in the contestant directory.

This sample satisfies the constraints of test points $5,6$.

Sample 12.

See industry/industry12.in and industry/industry12.ans in the contestant directory.

This sample satisfies the constraints of test points $7,8$.

Sample 13.

See industry/industry13.in and industry/industry13.ans in the contestant directory.

This sample satisfies the constraints of test points $9\sim 11$.

Sample 14.

See industry/industry14.in and industry/industry14.ans in the contestant directory.

This sample satisfies the constraints of test points $12\sim 14$.

Sample 15.

See industry/industry15.in and industry/industry15.ans in the contestant directory.

This sample satisfies the constraints of test points $15\sim 17$.

Sample 16.

See industry/industry16.in and industry/industry16.ans in the contestant directory.

This sample satisfies the constraints of test points $18,19$.

Sample 17.

See industry/industry17.in and industry/industry17.ans in the contestant directory.

This sample satisfies the constraints of test points $20,21$.

Sample 18.

See industry/industry18.in and industry/industry18.ans in the contestant directory.

This sample satisfies the constraints of test points $22\sim 24$.

Sample 19.

See industry/industry19.in and industry/industry19.ans in the contestant directory.

This sample satisfies the constraints of test point $25$.

Constraints

For all testdata:

• $2 \le n \le 10^5$.
• For all $1 \le i \le n-1$, $1 \le u_i, v_i \le n$, and $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ form a tree.
• $1 \le m \le 10^5$.
• $1 \le s, t, r \le n$, $o_x, o_y \in \{0,1\}$.

::cute-table{tuack}

Test point ID	$n, m \le$	$o_x$	$o_y$	$r$	Special property
$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$		None
$15 \sim 17$		$= 1$	$= 0$		^
$18, 19$		^	$= 1$		B
$20, 21$	$5 \times 10^4$		^		None
$22 \sim 24$	$10^5$				^
$25$	^	$\in \{0,1\}$

Special property A: There exists $1 \le x \le n$ such that for all $1 \le i \le n - 1$, we have $u_i = x$ or $v_i = x$.

Special property B: The unrooted tree formed by all devices is generated uniformly at random among all labeled unrooted trees on $n$ nodes.

Translated by ChatGPT 5