Hi I am currently trying to solve my first problem with segment tree. Link to the problem:http://www.hackerearth.com/tracks/pledge-2015-medium/xor-in-tree-1/
I couldn't understand the segment tree implementation in context to this problem which is present in the editorial in the problem setter's solution.
What does T[i] store here?
For the second query, why
int res = path_xor[u] ^ path_xor[v] ^ ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c];
and not
int res = ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c]; for the second query?
Currently, I could only understand that the tree is first ordered so that it becomes inline ie topological sort.Now the segment tree works on this topologically sorted tree.
Read about heavy path decomposition and then return to this problem.
But the solution in the editorial using segment tree doesn't use heavy path decomposition.
Could you please help me with the setter's solution mentioned in the editorial?
I believe that HPD is used but it is not named.
Could you point to some good tutorial of HPD with implementation?
http://blog.anudeep2011.com/heavy-light-decomposition/
I believe, in this problem euler tour + LCA is good enough.
Heavy-light is overkilling...