You are given a tree \(T\) with \(N\) nodes rooted at \(1\). The \(i^{th}\) node of the tree has been assigned value \(A_i\). You are required to handle two types of queries:
- \(\text{1 v x}:\) Update the value of node \(\text{v}\) to \(\text{x}\), that is \(A_\text{v} = x\).
- \(\text{2 v}:\) Consider the multiset of values of nodes present in the subtree of node \(\text{v}\). Consider all non-empty subsets of this set. Alice and Bob play a game on each of these subsets (independently) alternating turns.
- For each subset, Alice starts the game. In each turn, the current player must choose some element of the current subset and reduce it to some non-negative element. The player who cannot make a move loses. Note that it is necessary to reduce or decrease the element.
- You need to find the number of subsets where Bob is guaranteed to win. The number of subsets can be very large, output it modulo \(1000000007(10^9+7)\)
Input format
- The first line contains an integer that denotes the number of nodes in tree \(T\).
- The second line contains \(N\) space-separated integers denoting the initial value on the nodes of the tree(\(A_i\))
- \((N - 1)\) lines follow. Each of these lines contains two space-separated integers \(u\) and \(v\) denoting that there is an edge between these two nodes.
- The next line contains an integer \(Q\) denoting the number of queries.
- \(Q\) lines follow. Each line is a query of the type \(\text{1 v x}\) or \(\text{2 v}\).
Output format
For each query of type \(\text{2 v}\), print the number of non-empty subsets of the multiset of values present in a subtree of node \(\text{v}\) when Bob wins.
Constraints
We have \(N = 4\). The values on nodes are: \(A_1 = 1, A_2 = 2, A_3 = 3, A_4 = 3\). Next, \(Q = 3\).
The first query is of the type \(\text{2 1}\). Consider the multiset of values of nodes present in subtree of node \(1\). The multiset is \(S = \text{{1, 2, 3, 3}}\). Consider the subset \(\text{{1}}\). Alice starts the game and can reduce it to \(\text{{0}}\). Now, Bob cannot reduce it further and so Alice wins. The \(3\) non-empty subsets of \(S\) where Bob wins are \(\text{{1, 2, 3}, {1, 2, 3}, {3, 3}}\). Note that \(\text{{1, 2, 3}}\) is repeated twice because \(\text{{3}}\) appears twice.
The second query is of the type \(\text{1 4 4}\). We update the value of \(A_4\) to \(4\). Therefore, the array becomes \(A = [1, 2, 3, 4]\).
The third query is again of the type \(\text{2 1}\). Consider the multiset of values of nodes present in subtree of node \(1\). The multiset is \(S = \text{{1, 2, 3, 4}}\). There is only \(1\) non-empty subset of multiset \(S\) where Bob wins which is \(\text{{1, 2, 3}}\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor