Description

Xiao V has $n$ problems. His problems are very tricky, so the caring contestant ufozgg plans to weaken them. To avoid being weakened, Xiao V hides all his tricky problems in a tree with $n$ nodes (nodes are numbered from $1$ to $n$). Every node on the tree corresponds one-to-one with one of Xiao V’s problems. Each problem has a “trickiness value.” The problem corresponding to node $i$ (meaning the node labeled $i$ in the tree, same below) has trickiness value $a_i$.

To protect his problems, the magician Xiao V cast a spell on the tree. From then on, anyone who wants to explore the tree must perform jump operations on it. Each jump operation includes a start $s$, an end $t$, and a step size $k$. This means the jumper will start from $s$ and reach $t$ by jumping along the simple path on the tree. In each jump, if the shortest path distance from the current node to $t$ is no more than $k$, the jumper jumps directly to $t$; otherwise, the jumper advances exactly $k$ edges along the shortest path toward $t$.

Since Xiao V hid the problems in the tree, ufozgg cannot weaken them directly. He must jump on the tree and weaken problems along the way. Every time ufozgg passes through a node (including the start $s$, even when $s=t$), he will take the square root of that node’s problem’s trickiness value and round it down: that is, if he passes node $i$, he sets $a_i = \lfloor \sqrt{a_i} \rfloor$. We call this a weaken operation.

From time to time, ufozgg also wants to know how much he has weakened the problems. Therefore, in some jump operations he gives up weakening and instead computes the sum of trickiness values of the nodes visited in that jump. We call this a query operation.

The onlooker Lülü is very interested in Xiao V’s tricky problems and ufozgg’s weakening plan. He now wants to know the result ufozgg gets for each query operation. Can you help him?

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The next line contains $n$ space-separated positive integers $a_1, a_2, \ldots, a_n$, describing the trickiness value on each node.

The next $n-1$ lines describe the tree. Each line contains two positive integers $u, v$, describing an edge $(u, v)$. It is guaranteed that $1 \le u, v \le n$, and that these $n-1$ edges form a tree.

The next line contains a positive integer $Q$, the total number of operations performed by ufozgg.

The next $Q$ lines describe each operation in the order they are performed. Each line contains four space-separated integers $op, s, t, k$, meaning the jump starts at $s$, ends at $t$, with step size $k$. If $op = 0$, it is a weaken operation; if $op = 1$, it is a query operation.

Output Format

For each query operation, output a single line with one integer, the sum of the trickiness values of all problems counted in that operation.

5
1 2 3 4 5
1 2
2 3
3 4
2 5
5
1 1 4 1
1 1 4 2
0 1 5 2
1 2 4 5
1 1 5 1

10
8 6 5

Hint

For $100\%$ of the testdata, $n \le 50000$, $Q \le 400000$, $1 \le a_i \le 10^{13}$.

For all operations, it is guaranteed that $0 \le op \le 1$ and $1 \le s, t, k \le n$.

Translated by ChatGPT 5