Illusion Tree

All submissions for this problem are available.
Given a graph with $N$ nodes and $N  1$ edges. Every node has value given by array $A$. Now you need to process queries of the following two types  * $1$ $V$ $X$  Change the value of node $V$ to $X$ * $2$ $V$ $K$  Find the sum of all values which occur **odd number of times** in path from vertex $V$ to its $K^{th}$ ancestor. If $K^{th}$ ancestor doesn't exist, take it $1$. **Note:** It is guaranteed that given graph is a tree. Take root of the tree as **1**. ### Input * **First line:** $N$ and $Q$, defining no of nodes and no of queries. * **Second line:** $N$ space separated integers defining array $A$. * **Next N  1 lines:** $u$ and $v$, which means there is an edge between vertex $u$ and vertex $v$. * **Next Q lines:** Queries of either of the two types as explained above. ### Output For each query of **Type 2**, you need to print the required sum in a new line. ### Constraints * $1$ $\leq$ $N$, $Q$ $\leq$ $2 \cdot 10^{5}$ * $1$ $\leq$ $u$, $v$, $K$ $\leq$ $N$ * $0$ $\leq$ $A_i$, $X$ $\leq$ $25$ ### Example Input ``` 8 4 1 3 2 5 3 5 4 5 1 2 1 3 2 4 2 5 5 6 6 7 4 8 2 6 2 2 8 3 1 1 3 2 7 4 ``` ### Example Output ``` 5 4 12 ``` ### Explanation For 1st query, 2nd ancestor of 6 is 2, and values in path are [5, 3, 3]. Sum of values that occur odd times = 5. For second query, 3rd ancestor of 8 is 1 and values are [5, 5, 3, 1]. So, sum of values is 3 + 1 = 4. Now for fourth query, 4th ancestor of 7 is 1, and values in path are [4. 5, 3, 3, 3]. So ans is 4 + 5 + 3 = 12. As they all occur odd no of times.Author:  nine_tails9 
Tags  nine_tails9 
Date Added:  31012019 
Time Limit:  1  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions