Can anyone tell me how to approach this question with detailed explanation for 100 score?
This problem can be solved using Heavy light decomposition . In the given problem we are given a tree and some queries, so we can decompose our tree into chains using heavy light decomposition and using segment trees we can query the chains very easily in O(logn) time. If you don’t know about heavy light decomposition please google it and understand it first and then implement it by yourself.
Happy Coding 
Time limit of your solution is too high. Hope for more optimised solution.
How do you answer the query of “XOR of all numbers less than K” ?? If had been count of all numbers, its easily done via upper bound or lower bound, but how will you answer XOR? What are you storing in nodes of the tree??
For the queries, I just sorted the queries and edge weights together based on the value of k (or edge weight) and whenever an edge weight comes up we can just update the segment tree and whenever there is a query we query the segment tree and the answer for the query is stored .
1 Like
I just implemented HLD for the first time and used this tutorial as guide:
It solves almost exactly the same problem. Just replace the addition with xor and sort queries and updates together.
I used tree flattening plus segtree.
1 Like
I’ve answered here https://discuss.codechef.com/questions/105341/need-solution-for-2-problem-from-july-long/105391.
I used square root decomposition to decompose the tree.
I also used it but I was getting root n*log(root n) per query which was giving TLE. What was your approach?
1 Like