#P9887. Capoo on tree

    ID: 8109 传统题 20000ms 512MiB 尝试: 11 已通过: 2 难度: 9 上传者: 标签>CF2700树链剖分线段树可持久化数据结构DFSLCA2023“钉耙编程”中国大学生算法设计超级联赛(9)

Capoo on tree

Capoo on tree

Problem Description

Bugcat Capoo planted an apple tree at his doorstep, which has a total of nn nodes, and on the ii-th node, an apple of size aia_i grows. Capoo observes and records the growth of the apples every day. He discovers that: On the ii-th day, if it's raining, all apples of size xix_i on the chain from node uiu_i to node viv_i on the tree would grow by 11 unit; If it's cloudy, all apples of size xix_i on the chain from node uiu_i to node viv_i on the tree would shrink by 11 unit; If it's sunny, then Capoo goes out to check the quality of the apples on the tree. Capoo believes that only apples exceeding size yiy_i are up to standard apples. He would climb from node uiu_i to node viv_i on the tree, checking all the apples along the path. When Capoo continuously encounters lil_i qualifying apples, he gets very happy and records the distance from the starting position pip_i to the starting node uiu_i, then stops checking. Otherwise, if there is no set of lil_i consecutive up-standard apples on the entire path, Capoo gets disappointed and creates a scene. However, Capoo inadvertently lost all the records of pip_i. Now, he comes to you with growth records of a total of mm days, hoping to find out the distance disidis_i from the recorded position pip_i to the starting point that he recorded each sunny day he went out to inspect, or to confirm if such a position does not exist. Formally speaking, for an unrooted tree (V,E)(V, E) of size nn with node ii having a weight of aia_i, you need to support the following operations: If we represent the path from uiu_i to viv_i on the tree as

$$path_T(u_i, v_i) = \{p_0, p_1, \cdots, p_k| p_0 = u, p_k = v, (p_i, p_{i + 1})\in E\}$$

That is, we use pip_i to represent the ii-th point on the path, then operations can be expressed as:

  • 11 uiu_i viv_i xix_i, for each point pjp_j satisfying apj=xia_{p_j}=x_i, update apja_{p_j} to apj+1a_{p_j} + 1
  • 22 uiu_i viv_i xix_i, for each point pjp_j satisfying apj=xia_{p_j}=x_i, update apja_{p_j} to apj−1a_{p_j} - 1
  • 33 uiu_i viv_i lil_i yiy_i, seek the minimum jj that satisfies ∀k∈[0,li),apj+k≥yi\forall k \in [0, l_i), a_{p_{j + k}} \geq y_i

Input

The first line contains a positive integer T(1≤T≤100)T(1\leq T \leq 100), indicating the number of test cases. For each of the next TT test cases, the format is: The first line contains two positive integers n(2≤n≤5∗105),m(1≤m≤5∗105)n(2\leq n \leq 5*10^5), m(1\leq m \leq 5*10^5), which represent the total number of nodes on the tree and the number of operations, respectively. The next line contains nn integers, where the ii-th integer ai (1≤ai≤n)a_i\ (1\leq a_i\leq n) represents the weight of node ii. The next n−1n-1 lines consist of two integers ui,vi(1≤ui,vi≤n)u_i, v_i(1\leq u_i, v_i \leq n) each, indicating an edge on the tree. The following mm lines represent mm operations, where the first integer op(1≤op≤3)op(1\leq op \leq 3) of each line indicates the type of operation.

  • If op=1op=1, then the next three integers ui,vi,xi(1≤ui,vi≤n,1≤xi<n)u_i,v_i,x_i(1\leq u_i, v_i \leq n, 1\leq x_i < n) represent increasing the weight of all nodes with value xix_i on the path from uiu_i to viv_i by one.
  • If op=2op=2, then the next three integers ui,vi,xi(1≤ui,vi≤n,1<xi≤n)u_i,v_i,x_i(1\leq u_i, v_i \leq n, 1 < x_i \leq n) represent decreasing the weight of all nodes with value xix_i on the path from uiu_i to viv_i by one.
  • If op=3op=3, then the next four integers ui,vi,li,yi(1≤ui,vi,li,yi≤nu_i,v_i,l_i,y_i(1\leq u_i, v_i, l_i, y_i \leq n) ask for the distance from node uiu_i to the closest chain with a length of lil_i and node weights greater than or equal to yiy_i on the path from uiu_i to viv_i. It is guaranteed that ∑n≤106,∑m≤106\sum n \leq 10^6,\sum m \leq 10^6.

Output

For each query, output a line with a positive integer disdis indicating the calculated distance. If the corresponding chain does not exist, output -1.

Sample Input

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

Sample Output

-1
0
-1
3

Source

2023“钉耙编程”中国大学生算法设计超级联赛(9)