407644: GYM102862 H Optimize DFS

Memory Limit：256 MB Time Limit：3 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

H. Optimize DFStime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a tree with $$$n$$$ vertices. Every vertex $$$v$$$ has two values $$$a_v$$$ and $$$b_v$$$. You have to process $$$q$$$ queries of types:

  1. Given $$$v$$$ and $$$x$$$, assign $$$a_v = x$$$;
  2. Given $$$v$$$, print $$$a_v$$$;
  3. Given $$$v$$$, implement the following procedure efficiently:

    First, create an array $$$\text{used}[1\ldots n]$$$ filled with false initially. Then run the function $$$\text{DFS}(v)$$$: 


        DFS(v):
        {
            used[v] = true;
            for u from 1 to n do
            {
                if (u and v are connected by an edge)
                   and (used == false)
                   and (a[v] + b[to] == a[to] + b[v]) then
                {
                    DFS(to);
                }
            }
            a[v] = b[v];
        }
Note that the array $$$\text{used}$$$ is independent for each query of the 3rd type.Input

The first line contains two integers $$$1 \leq n, q \leq 5 \cdot 10^5 $$$. The second line contains $$$n$$$ integers, where the $$$i$$$-th is the initial value of $$$a_i$$$ ($$$0 \leq a_i \leq 5\cdot10^5$$$). The third line contains $$$n$$$ integers, where the $$$i$$$-th is the value of $$$b_i$$$ ($$$0 \leq b_i \leq 5\cdot10^5$$$).

Each of the next $$$n-1$$$ lines describes an edge of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$), the indices of the vertices connected by the $$$i$$$-th edge. It is guaranteed that the given graph is a tree.

The next $$$q$$$ lines contain the description of the queries. The $$$i$$$-th query starts with an integer $$$t_i$$$ ($$$1 \leq t_i \leq 3$$$) that denotes the type of the query. If $$$t_i = 1$$$, then two integers $$$v_i$$$ and $$$x_i$$$ follow ($$$1 \leq v_i \leq n$$$, $$$0 \leq x_i \leq 5\cdot10^5$$$). Otherwise only $$$v_i$$$ is given.

Output

For each query of the 2nd type output one integer, the value $$$a_v$$$.

ExamplesInput
2 6
20 102
10 90
1 2
2 1
2 2
1 2 100
3 1
2 1
2 2
Output
20
102
10
90
Input
6 6
20 30 30 60 60 70
10 20 30 40 50 60
1 2
2 4
2 5
1 3
3 6
1 3 40
3 1
2 1
2 6
2 2
2 4
Output
10
60
20
60

Source/Category

加入题单

算法标签：