problem link: https://www.codechef.com/MAY17/problems/GPD
Can any one explain , how to use heavy light decomposition in this problem?
Firstly, i know a persistent approach was sufficient but i am just curious!
Now , i have learned that we can use heavy light decomposition in a tree in order to break paths into heavy ( long paths) edges and light edges(short paths) , i know how it achieves log(n) factor too. In this problem , i can use heavy light decomposition in the given tree and also can use segment tree of tries to query longer chains but problem is we also have an add query too. So,how to maintain our heavy light topology when new nodes are coming in ?
(Okay , one approach would be to use offline queries to compute whole topology initially and then use heavy-light but then also they are encoded , so we cannot tell which node is added where and it’s key)