Author: Ankit Kathuria
Tester: Akshay Sharma
Editorialist: Ankit Kathuria
Recursion ,Tree traversal
Given a tree, find the weight of shortest path that exist between any two nodes…
for each node calculate the shortest path that starts from that node. This calculation can be done recursively starting from the leaf nodes in a bottom to top manner. The least of these values will be the answer,
for each pair calculate the difference of destruction factor and find the minimum.The time complexity is O(N^2) and hance will not be accepted for higher test cases…
We are given a tree
Edge length between two nodes will be the difference of destruction factors between the nodes.
Difference of destruction factor between two nodes can be seen as a sum of edge lengths(weight of path) in a path connecting the two nodes.
for each of the node N we calculate the weight of the shortest path that starts from N
F(N)= weight of shortest path that starts from N to K(any predecessor of N)
we have to calculate F(N) for every N and find the minimum of all those values.
To calculate F(N), we can either iterate from 1 to n and then getting the weight of the shortest path but that would take O(N) time. and we have to repeat it n times i.e for each node. so The time complexity would be O(N^2) which would be fairly large when N<=100000.
calculate the value of F(N) for each of the children of the N.lets say K1,K2,K3…
and then calculate F(N) using all those values.
F(N)= min(E[N,K1]+F(K1), E[N,K2]+F(K2) , E[N,K3]+F(K3),… )
where E[a,b] = edge length from a to b
code would look something like this.
int F( N ) //stores and return the value of F(N)
if(N is leaf node) a[N]=INFINITY; return INFINITY; min=INFINITY; for each children K of N if(getf(K)+D[N]-D[K]<=min) min=getf(K)+D[N]-D[K] a[N]=min; return min;
calling F(root) will fill the array completely for each of the nodes,now we have to just iterate the array a and get the minimum value that will be the answer
Time Complexity : O(N) as we have to just traverse the whole tree once to get the F(N) for each node.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.