REL203 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice 
Contest

Author: Divyesh Savaliya 
Editorialist: Divyesh Savaliya

DIFFICULTY:

Medium

PREREQUISITES:

Tree, DFS

PROBLEM:

You are given weighted undirected tree with N nodes [1,N]. Consider the weight as a distance between two nodes. Now, you are at node 1 and want to visit all nodes. So, find the minimum distance you have to travel such that all nodes are visited. You can travel more than one time through any edge.

EXPLANATION:

Problem is tricky, but solution is very simple. You are given weighted tree with N nodes and you have to visit all nodes starting from node 1. Since it is tree, so there is only one unique path between any two nodes. So, in order to visit all nodes you must have to travel through every edges two times except the edges which are part of path from node 1 to any one leaf. why?

Let’s take an example:

You have tree with five node. Root of tree is node 1. Node 2 and Node 3 are children of Node 1. Node 4 is child of node 2 and node 5 is child of node 3. Now, you are at node 1. To visit all five nodes, you have two ways to travel.

  1. 1->2->4->2->1->3->5
    Go to node 2 from node 1.
    Go to node 4 from node 2.
    Return from node 4 to 2.
    Return from node 2 to 1.
    Go to node 3 from node 1.
    Go to node 5 from node 3.

  2. 1->3->5->3->1->2->4
    Go to node 3 from node 1.
    Go to node 5 from node 3.
    Return from node 5 to 3.
    Return from node 3 to 1.
    Go to node 2 from node 1.
    Go to node 4 from node 2

Now, in first way, edges come in path from node 1 to node 5 are travelled only once while all other edges are travelled two times.
Similarly, in second way, edges come in path from node 1 to node 4 are travelled only once while all other edges are travelled two times.

So, it is proved through above example that you have to travel through all edges two times except the edges come in the path from root to any one leaf.

Now, there are multiple way to visit all nodes because tree may have more than one leaf. In order to find the minimum total distance, you have to consider the solution or way which has the maximum distance path which is travelled one time. i.e. the solution of the given question is sum of distance of all edges multiplied by 2 minus the longest path from node 1 to leaf (i.e. sum of distance of edge come in path from node 1 to leaf.) why? because you must have to travel all edges two time except one path. So, if you make that path as costly as possible, the total distance travelled by you become minimum.

Now, how to find longest path from root to leaf having maximum cost. Just run dfs from node 1 with one extra variable (cst). See author’s or tester’s solution given below.

Time complexity is same as DFS.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.