### PROBLEM LINK:

**Author:** Ankit Kathuria

**Tester:** Akshay Sharma

**Editorialist:** Ankit Kathuria

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Recursion ,Tree traversal

### PROBLEM:

Given a tree, find the weight of shortest path that exist between any two nodes…

### QUICK EXPLANATION:

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,

### EXPLANATION:

Naive approach:

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…

Better approach

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.

i->j->k

E[i,k]=D[i]-D[k]=(D[i]-D[j])+(D[j]-D[k])=E[i,j]+E[j,k]

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.

Calculate F(N):

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.

Better method:

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.