Tree Maximum :
Difficulty Level : Hard
Submissions : 112
Asked In :
Marks :20
: 2 | : 0
You are given a rooted tree consisting of $$$n$$$ nodes. The nodes are numbered $$$1,2,…,n,$$$ and node $$$1$$$ is the root. Each node has a value associated with it.
Your task is to process following types of queries:
- change the value of node $$$s$$$ to $$$x$$$.
- calculate the maximum of values of nodes contained in the subtree of node $$$s$$$.
The first input line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n,q \le 2 \cdot 10^5)$$$ — the number of nodes and queries. The nodes are numbered $$$1,2,…,n$$$.
The next line has $$$n$$$ integers $$$v_1,v_2,…,v_n$$$ $$$(1 \le v_i \le 10^9)$$$ — the value of each node.
Then there are $$$n−1$$$ lines describing the edges. Each line contains two integers $$$a$$$ and $$$b$$$ $$$(1 \le a,b \le n)$$$ — denoting that there is an edge between nodes $$$a$$$ and $$$b$$$.
Finally, there are $$$q$$$ lines describing the queries. Each query is either of the form "1 s x" or "2 s" $$$(1 \le s \le n, 1 \le x \le 10^9)$$$.
Print the answer to each query of type $$$2$$$.
5 3 4 2 5 2 1 1 2 1 3 3 4 3 5 2 3 1 5 6 2 3
5 6
