Hello all,
I am trying to solve this problem
https://www.hackerrank.com/contests/101hack19/challenges/journey-scheduling
Editorial for this problem mentioned that the query for the longest distance for any given node in a tree can be performed with standard DP approach ... I am not familiar with the approach and also unable to find content regarding this on internet so please can anyone help me understanding this .. or provide me link for good tutorial for this standard approach with reference to some more problem ...
Thanx in advance ..
Hi, with second time distance is diametr of tree.
Yes you are absolutely correct but actually i need to query first for the longest distance that i can traversed from current position / current node . I want to know approach of finding that .. Please help if you can ..
the longest distance from any node is always to travel to one of diameter ends ,if there are more than one diameter choose any one of them
@kingofnumbers
Can you please elaborate this a bit more.. I am getting whatever you are saying .. but still need more clarification ..
This is what i have understood that we can first find the diameter of the tree which can be calculated using a single call to DFS easily (also maintain the start point and end point right)then for each node i will find the distance of this to both of the end point and end point which will give me maximum answer is the answer to the query right.. For this purpose i can use DP LCA ...
Each query taking log(n) time so the total complexity is Q(log(N))..
I understood this ... But i read in the editorial that this can be done V+E. Is the idea first find the two end points and then do DFS two time one for each point..
Or even easier , you don't need LCA here's what you should do:
find the diameter of the tree , this step needs doing dfs twice.
now suppose the end points of the diameter are nodes v and u , do dfs from u to calculate the distance to u from all other nodes. do dfs from v to calculate the distance to v from all other nodes
now for each node you have two values , the distance from it to v and to u , so for each node take the maximum of these two values , this is what you need.
Thanx i mentioned this at the end of the above comment and i dont think we need twio dfs to find the diameter with start point u and v we can do that using only one dfs isn't it ??
yes if you used the dp way for finding the diameter,
there's another way to find the diameter by picking some random node v then go to farthest node from v call it u then go to farthest node from u call it w , now u and w are ends of diameter.
@kingofnumbers
Can you please post some related problem or some good tutorials related to tree terminologies... my mean such kinds of terminologies .. :D
thanx
dreaming IOI 2013