Red Blue Tree
Contest: Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: data structures, implementation, trees

You are given a tree of $$$n$$$ nodes. The tree is rooted at node $$$1$$$, which is not considered as a leaf regardless of its degree.

Each leaf of the tree has one of the two colors: red or blue. Leaf node $$$v$$$ initially has color $$$s_{v}$$$.

The color of each of the internal nodes (including the root) is determined as follows.

- Let $$$b$$$ be the number of blue immediate children, and $$$r$$$ be the number of red immediate children of a given vertex.
- Then the color of this vertex is blue if and only if $$$b - r \ge k$$$, otherwise red.

Integer $$$k$$$ is a parameter that is same for all the nodes.

You need to handle the following types of queries:

- 1 v: print the color of node $$$v$$$;
- 2 v c: change the color of leaf $$$v$$$ to $$$c$$$ ($$$c = 0$$$ means red, $$$c = 1$$$ means blue);
- 3 h: update the current value of $$$k$$$ to $$$h$$$.

Input format:
The first line of the input consists of two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^{5}$$$, $$$-n \le k \le n$$$) — the number of nodes and the initial parameter $$$k$$$.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting that there is an edge between vertices $$$u$$$ and $$$v$$$.

The next line consists of $$$n$$$ space separated integers — the initial array $$$s$$$ ($$$-1 \le s_i \le 1$$$). $$$s_{i} = 0$$$ means that the color of node $$$i$$$ is red. $$$s_{i} = 1$$$ means that the color of node $$$i$$$ is blue. $$$s_{i} = -1$$$ means that the node $$$i$$$ is not a leaf.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of queries.

$$$q$$$ lines follow, each containing a query in one of the following queries:

- 1 v ($$$1 \le v \le n$$$): print the color of node $$$v$$$;
- 2 v c ($$$1 \le v \le n$$$, $$$c = 0$$$ or $$$c = 1$$$): change the color of leaf $$$v$$$ to $$$c$$$ ($$$c = 0$$$ means red, $$$c = 1$$$ means blue). It is guaranteed that $$$v$$$ is a leaf;
- 3 h ($$$-n \le h \le n$$$): update the current value of $$$k$$$ to $$$h$$$.

Output format:
For each query of the first type, print $$$0$$$ if the color of vertex $$$v$$$ is red, and $$$1$$$ otherwise.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
Figures:(i) The initial tree (ii) The tree after the 3rd query (iii) The tree after the 7th query

Example input:
5 2
1 2
1 3
2 4
2 5
-1 -1 0 1 0
9
1 1
1 2
3 -2
1 1
1 2
3 1
2 5 1
1 1
1 2

Example output:
0
0
1
1
0
1

Editorial:
• Transform queries into two types: "change color of a leaf", and "answer color of some vertex if k is given".
• Note that when $$$k = -\infty$$$ all internal vertices are red. When increasing $$$k$$$, each vertex will change its color exactly once, let's call this value of $$$k$$$ as boundary value for this vertex.
• If we can keep boundary values for all vertices, answering queries is easy.
• Let's do sqrt decomposition on queries: group them in blocks and process in blocks of size $$$m$$$.
• When starting a block, compress the tree so that there are $$$O(m)$$$ interesting vertices: vertices involved in queries and LCAs of them.
• Let's call subtrees without interesting vertices as outer subtrees. We can compute the boundary values for all vertices in outer subtrees once for each block since the colors of leaves do not change.
• Now we should compress the paths between the interesting vertices. Note that the boundary values on a path only depend on the color of the vertex in the bottom end of the path. So for each such path compute two boundary values: if the vertex in the bottom end is red or blue.
• Now we can process queries by using the corresponding values of boundary values, going down-up.
• Straightforward implementation leads to $$$O(n\log{n})$$$ preprocessing of each block and $$$O(m\log{n})$$$ query time, meaning the overall complexity is $$$O((n + q) \sqrt{n + q} \log{n})$$$. The logarithms are from sorting and binary search, respectively, so this solution is already fast enough to get AC.
• To implement compression in $$$O(n)$$$ you need to go from lowest to highest possible $$$k$$$ and maintain which vertices are red in outer subtrees. Note that the number of different boundary values is $$$O(n)$$$, so you can store for each $$$k$$$ the list of vertices having this boundary value.
• To implement queries in $$$O(m)$$$, you need to precompute binary search outcomes for the given $$$O(m)$$$ values while computing the boundary values.
• This way the overall complexity becomes $$$O((n + q) \sqrt{n + q})$$$.