Pishty and Tree: JULY17: Help

Can anyone tell me how to approach this question with detailed explanation for 100 score?

https://www.codechef.com/JULY17/problems/PSHTTR

I solved it using persistent segment tree.
It was a mix of COT and KQUERY.

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 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
//