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

加入题单

上一题 下一题 算法标签: