J. Tree
time limit per test
4 seconds
memory limit per test
1024 MB
input
standard input
output
standard output

You are given a rooted tree with root $$$1$$$ and $$$N$$$ nodes. Each node $$$i$$$ has an initial weight $$$M_i$$$. At all times, the system strictly maintains the following property: for any non-root node $$$x$$$, its weight never exceeds that of its parent, that is, $$$M_{\text{parent}(x)} \ge M_x$$$.

You need to process $$$Q$$$ operations online. The operations are of the following two types:

  • 1 u w: Query. Starting from node $$$u$$$, move upward along the tree edges toward the root, and find the first node whose weight is at least $$$w$$$ (including $$$u$$$ itself). Output the index of that node. If no such node exists all the way up to the root, output -1.
  • 2 x v: Update. Attempt to add $$$v$$$ to the weight of node $$$x$$$ ($$$v$$$ may be negative), that is, let $$$M_x \leftarrow M_x + v$$$. To avoid violating the tree property, a legality check must be performed before the update:
    • If $$$x \neq 1$$$ and $$$M_x + v \gt M_{\text{parent}(x)}$$$, then the update fails.
    • If $$$x$$$ is not a leaf node and $$$M_x + v \lt \max_{y \in \text{children}(x)} M_y$$$, then the update fails.
    If both checks pass, then the update is actually performed and SUCCESS is output; otherwise, the update is rejected, the state of the tree remains unchanged, and FAILED is output.
Input

The input contains multiple test cases.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), denoting the number of test cases.

For each test case, the first line contains two integers $$$N, Q$$$.

The second line contains $$$N$$$ integers $$$M_1, M_2, \dots, M_N$$$, and it is guaranteed that the initial weights satisfy the property described above.

The next $$$N - 1$$$ lines each contain two integers $$$u, v$$$, representing an edge in the tree.

The following $$$Q$$$ lines each contain three integers $$$opt, a, b$$$, representing an operation: when $$$opt = 1$$$, it denotes a 1 u w operation; when $$$opt = 2$$$, it denotes a 2 x v operation.

Constraints:

  • $$$1 \le N, Q \le 10^5$$$
  • $$$0 \le M_i, w \le 10^9$$$
  • $$$-10^9 \le v \le 10^9$$$
  • It is guaranteed that $$$M_i \ge 0$$$ at all times
It is guaranteed that for each test file, the sum of all $$$N$$$ and the sum of all $$$Q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$, respectively.
Output

For each test case, output $$$Q$$$ lines, each corresponding to the result of one operation:

  • For a 1 u w operation, output the index of the node satisfying the condition; if no such node exists, output -1.
  • For a 2 x v operation, output SUCCESS if the update succeeds, and FAILED if the update fails.
Example
Input
1
5 6
100 80 50 30 20
1 2
1 3
2 4
2 5
1 4 40
1 5 150
2 2 30
2 2 -60
2 4 10
1 4 40
Output
2
-1
FAILED
FAILED
SUCCESS
4
Note

In the sample, the tree structure is as follows: node $$$1$$$ has children $$$2$$$ and $$$3$$$; node $$$2$$$ has children $$$4$$$ and $$$5$$$.

The initial weights are $$$M = [100, 80, 50, 30, 20]$$$.

  • Operation 1 1 4 40: starting from node $$$4$$$, we move upward to find a node whose weight is at least $$$40$$$. The current weight of node $$$4$$$ is $$$30 \lt 40$$$, while its parent node $$$2$$$ has weight $$$80 \ge 40$$$, which satisfies the condition, so the output is 2.
  • Operation 2 1 5 150: starting from node $$$5$$$, we move upward to find a node whose weight is at least $$$150$$$. None of the nodes on the path, including the root node $$$1$$$ (whose weight is $$$100$$$), satisfies the condition, so the output is -1.
  • Operation 3 2 2 30: we attempt to increase the weight of node $$$2$$$ by $$$30$$$, so the new weight would be $$$110$$$. Since $$$110 \gt M_1$$$ ($$$100$$$), this violates the property that a parent's weight must be at least that of its child, so the update fails and the output is FAILED.
  • Operation 4 2 2 -60: we attempt to decrease the weight of node $$$2$$$ by $$$60$$$, so the new weight would be $$$20$$$. Since $$$20 \lt \max(M_4, M_5)$$$ ($$$30$$$), this also violates the monotonicity property of the tree weights, so the update fails and the output is FAILED.
  • Operation 5 2 4 10: we attempt to increase the weight of node $$$4$$$ by $$$10$$$, so the new weight becomes $$$40$$$. This satisfies $$$40 \le M_2$$$ ($$$80$$$), and node $$$4$$$ is a leaf node, so the update succeeds. We update $$$M_4 = 40$$$ and output SUCCESS.
  • Operation 6 1 4 40: again starting from node $$$4$$$, we move upward to find a node whose weight is at least $$$40$$$. Since the previous update succeeded, we now have $$$M_4 = 40 \ge 40$$$, so node $$$4$$$ itself already satisfies the condition, and the output is 4.