P9126 - Capoo on tree

内存限制：512 MB 时间限制：20 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：0

    Bugcat Capoo planted an apple tree at his doorstep, which has a total of n nodes, and on the i-th node, an apple of size a_i grows. Capoo observes and records the growth of the apples every day. He discovers that:
    On the i-th day, if it's raining, all apples of size x_i on the chain from node u_i to node v_i on the tree would grow by 1 unit;
    If it's cloudy, all apples of size x_i on the chain from node u_i to node v_i on the tree would shrink by 1 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 y_i are up to standard apples. He would climb from node u_i to node v_i on the tree, checking all the apples along the path. When Capoo continuously encounters l_i qualifying apples, he gets very happy and records the distance from the starting position p_i to the starting node u_i,then stops checking. Otherwise, if there is no set of l_i consecutive up-standard apples on the entire path,Capoo gets disappointed and creates a scene.
    However, Capoo inadvertently lost all the records of p_i. Now, he comes to you with growth records of a total of m days, hoping to find out the distance dis_i from the recorded position p_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) of size n with node i having a weight of a_i, you need to support the following operations:
    If we represent the path from u_i to v_i on the tree as
                        path_T (u_i, v_i) = {p₀, p₁, · · · , p_k|p₀ = u, p_k = v,(p_i, p_i+1) ∈ E}
    That is, we use p_i to represent the i-th point on the path, then operations can be expressed as:
    • 1 u_i v_i x_i, for each point p_j satisfying a_pj = x_i, update a_pj to a_pj + 1
    • 2 u_i v_i x_i, for each point p_j satisfying a_pj = x_i, update a_pj to a_pj − 1
    • 3 u_i v_i l_i y_i, seek the minimum j that satisfies ∀k ∈ [0, l_i), a_pj+k ≥ y_i

    The first line contains a positive integer T(1 ≤ T ≤ 100), indicating the number of test cases.
    For each of the next T test cases, the format is:
    The first line contains two positive integers n(2 ≤ n ≤ 10⁵), m(1 ≤ m ≤ 10⁵), which represent the total number of nodes on the tree and the number of operations, respectively.
    The next line contains n integers, where the i-th integer a_i (1 ≤ a_i ≤ n) represents the weight of node i.
    The next n−1 lines consist of two integers u_i, v_i(1 ≤ u_i, v_i ≤ n) each, indicating an edge on the tree.
    The following m lines represent m operations, where the first integer op(1 ≤ op ≤ 3) of each line indicates the type of operation.
    • If op = 1, then the next three integers u_i, v_i, x_i(1 ≤ u_i, v_i ≤ n, 1 ≤ x_i < n) represent increasing the weight of all nodes with value x_i on the path from u_i to v_i by one.
    • If op = 2, then the next three integers u_i, v_i, x_i(1 ≤ u_i, v_i ≤ n, 1 < x_i ≤ n) represent decreasing the weight of all nodes with value x_i on the path from u_i to v_i by one.
    • If op = 3, then the next four integers u_i, v_i, l_i, y_i(1 ≤ u_i, v_i, l_i, y_i ≤ n) ask for the distance from node u_i to the closest chain with a length of l_i and node weights greater than or equal to y_i on the path from u_i to v_i.
    It is guaranteed that ∑n ≤ 10⁶,∑m ≤ 10⁶.

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

-1
0
-1
3

2023杭电多校9

9126: Capoo on tree

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签