PROBLEM LINK :
Practice ,
Contest
PREREQUISITES : dfs , Segment trees , dp
PROBLEM : Given a tree with edges directed towards root and nodes having some ticket information which allows you to travel k units towards the root with cost w . Answer Q queries i.e output the minimum cost for travelling from a node x to root .
OBSERVATIONS: Consider the tree to be rooted at 1 , so now every node has a directed edge towards its parent except the root , which means there is a unique path from every node to the root 1. So if we solve the problem for one unique path or one node, we can extend it for other paths as well .
EXPLANATION:
Lets try to solve the problem for a node X at depth H from the root 1 . So for now forget the tree and think of it as a 1D vector V where you have all the H-1 nodes that are between root and node X . The nodes inside the vector are sorted in the order of increasing depth . Lets just denote DP[x] to be the minimum cost of travelling from node X to the root .
So now for the given node X , lets just iterate over all the tickets present at node X and DP state will be like this :
for(int i=0;i<total_tickets;i++) // loop 1
{
K=current_ticket_jump_info;
W=weight_ticket_info;
for(int j=V.size()-1;j>= max(0,V.size()-1-k);j++) //loop 2
{
DP[X]=min( DP[X] , DP[V[j]] + W );
}
}
Code Explanation : Loop 1 simply iterates over the tickets at x and for a given ticket we can move at max K steps upwards towards the root and as we have already stored those nodes in our vector V , we can iterate over it . so the inner loop moves over those K steps to find the minimum cost .
But how can we calculate vector V for every node x ? Here comes DFS in action :
void dfs(int u,int p)
{
V.push_back(u);
for(int i=0 ; i< adj[u].size() ; i++)
{
if(adj[u][i]==p)continue;
dfs(adj[u][i],u);
}
V.pop_back();
}
Code Explanation : what we are doing over here is pushing a node u to the vector V when we havenāt discovered the subtree of u and pop it when the whole subtree is discovered . Its obvious that u will always lie between the path of any node which is in subtree of u and root . And this also take cares of the sorted depth order . If you arenāt getting this , try to draw a few trees .
So the final code :
void dfs(int u,int p)
{
V.push_back(u);
for(int l=0 ; l< adj[u].size() ; l++)
{
if(adj[u][l]==p)continue;
int x =adj[u][l];
for(int i=0;i<total_tickets;i++) // loop 1
{
K=current_ticket_jump_info;
W=weight_ticket_info;
for(int j=V.size()-1;j>= max(0,V.size()-1-k);j++) //loop 2
{
DP[x]=min( DP[x] , DP[V[j]] + W );
}
}
dfs(adj[u][l],u);
}
V.pop_back();
}
Complexity: : Well the complexity is simply O(N+M*N) , Damn 
! we need optimisations 
OBSERVATIONS: if we look at the inner loop of the code which goes up to K times and we find the minimum of DP , this can be done using any data structure that supports RMQ + Point updates in O(logn) time . Which will make the total complexity to be O(N + MlogN) and that is cool .
So what we can do is build a segment tree that supports two operations . First : find the minimum element in range L,R and Second: update an elementās value to VAL. And obviously as we need to query for the minimum element between [H-K , H] so we will build the tree over height H .
//consider segment tree has already been built with every element to be infinity apart from element 1 , which will be 0 because at height 1 , root is present .
void dfs(int u,int p,int h)
{
updatetree(0,1,n,h,DP[u]); // update the tree element at position h with its DP value . remember , node u is at height h and tree is built on height so we will update h position in the tree and not u .
for(int l=0 ; l< adj[u].size() ; l++)
{
if(adj[u][l]==p)continue;
int x =adj[u][l];
for(int i=0;i<total_tickets;i++) // loop 1
{
K=current_ticket_jump_info;
W=weight_ticket_info;
DP[x]=query(0,1,n,max(1,h-K),h)+W;
}
dfs(adj[u][l],u,h+1);
}
updatetree(0,1,n,h,INFINITY); // update the tree at with element h with Infinity as we are done with its subtree .
}
Now just print DP[x] for every query . AC 
. For the actual code refer this .
For example :
This is the given tree .
So this will be our segment tree before DFS .
Now , we see for the given tree the longest path between any node and root is of 4 nodes and for computing DP[x] we just need all the DP values of the nodes which lie between x to root i.e for a given height there will be only one DP value . example : for calculating DP[7] , we need DP[1] , DP[2] , DP[4] and DP[1] is at height 1 , DP[2] is at height 2 , DP[4] is at height 3 . So during dfs and updations , at node 7 our segment tree will look like this :
Now at node 7 let there be a ticket with k=2 , w=1 . So now we will query for minimum value between height [2,4] and compute our DP[7] . Now 7 has no children and dfs starts rolling back , and we update height 3 in segment tree with infinity . now at node 5 DPs we require are only DP[1] , DP[2] . The scenario of segment tree will be like this :
Now Let the ticket available at node 5 be k=3 , w=7 . So now we query over segment tree between [1,3].
