All submissions for this problem are available.
Ms. Ghatak is a geek! Being a geek has side-effects as many of you might known. Geeks can never leave a problem unsolved be it in practice or during the
contest! As Ghatak has a date with Gandey, Please solve her problem ASAP!
Given an undirected tree with N nodes each Node having an initial value 0, you have to process Q queries which are of two types as described below.
- 1 u v c - Update the value of each Node on the Unique Simple path between u and v to XOR of c and Old value.(u can be equal to v)
- 2 u - Report the value at Node u.
Note large input test file. Use faster Input/Output methods such as scanf/printf over cin/cout in C++.
The first line contains two integers N and Q.
The following N-1 lines contain two integers u and v , indicating that there is an edge between u and v.
Next Q lines contain Queries of Either type as mentioned in the problem.
For each Query of type 2 you have to print the value at Node u.
- 1 ≤ N ≤ 10^5
- 1 ≤ Q ≤ 10^5
- 0 ≤ C ≤ 1023
Input: 2 2 1 2 1 1 2 1 2 2 Output: 1
The tree is 1-2 . Both Nodes are updated by Query 1 from 0 to 1. Hence the value at Node 2 at Query 2 is 1.
|Time Limit:||1.5 - 5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.