I need help on Pishty and Tree.
My approach:
Find LCA using RMQ using SparseTable. [Preprocessing : O(NlogN), Query : O(1)].
After finding LCA travel trough all edges between U—V. (No of Steps== No of Edges between U and V).
This approach passes upto Task 4 but not 5th.(TLE).
Any better approach???
I have written my approach here: https://discuss.codechef.com/questions/105341/need-solution-for-2-problem-from-july-long/105391.
I used Sparse table (for LCA) + HLD with fenwick tree to compute the xor quickly.
First, reorder the queries and edges by increasing order of xor value. Now the problem reduces to finding the xor sum of all edges on the path from u to v (more info below). We can handle that using a single point update-range query fenwick tree.
Initially, we set the xor value of all edges in the tree to 0.
Now, let’s say that we want to find the xor sum of edges with weight less than k from nodes u to v. We just set the xor values edges with xor value <= k to their original value. Now, the only edges that will be considered in the xor sum from node u to node v will be those with xor value <= k. We can handle this for each chain using fenwick tree as mentioned above (If you not familiar with HLD, you might need to read up on it).
Query for each chain will be O(logN) because of single query to fenwick tree. Now, we just use HLD to switch chains so that we only need to traverse a logarithmic distance from node u to node v. Time-complexity: O(Q*log^2(N) + NlogN).