You are an owner of a botanica. To design your botanica you have created a tree on the ground having big white color nodes and edges connecting them. Each node has a herb plant in it with takes y amount of water each day.
Q queries are given in the form A B X. you need to water the plants on the route from A to B(inclusive). You have X amount of water. Water is the maximum number of trees that you can water.
(queries are independent of each other)
My idea behind the solution - Decompose the tree. Create persistent segement tree for each chain(key for the segment tree would be y). For Finding the solution. We can do binary search over the chains between A and B over R amount of water supply.
The question is fine.
I did not understand your solution. Wont creating a persistent segment tree for each chain increase the complexity to O(NQlogn) ?
I could only think of some O(Qlog^3N) solution for this.
while creating the persistent segment tree, each node will result into log n insert operation in there respective chain. so overall complexity for creating persistent segment tree will be O(nlogn).
For binary search we have to do search on at max logn chains.
Therefore overall complexity will be O(nlogn + Q(log N)^2).
Please let me know if i am doing something wrong. Can i know your solution?
Is your solution not Qlog^3n ? Because binary searching for the maximum value is logn , inside the binary search , you visit and logn chains and for each chain you make a segment tree of no. of nodes <= maximum.
And why is the decomposition(i am assuming you are refering to heavy light) necessary? Cant we just split it based on the lca and deal with 2 chains and find the answer directly? That will be Q(log^2N) i think.
I am doing heavy light decomposition and creation of persistent segment tree as a part of pre-processing.
If we just split it on the basis of lca into 2 chains, then how will you trace the state of nodes in that path? Won’t making chain cost addition factor of O(n) in your solution?