407644: GYM102862 H Optimize DFS
Description
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:
- Given $$$v$$$ and $$$x$$$, assign $$$a_v = x$$$;
- Given $$$v$$$, print $$$a_v$$$;
- 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];
}
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.
OutputFor each query of the 2nd type output one integer, the value $$$a_v$$$.
ExamplesInput2 6 20 102 10 90 1 2 2 1 2 2 1 2 100 3 1 2 1 2 2Output
20 102 10 90Input
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 4Output
10 60 20 60