Trivalling sells man problem

#1

implement part ,i don’t understand

#2

@khemchandrs
We use a modified DFS traversal to solve this problem. The problem uses the concepts of both graph theory and pigeonhole principle as explained in the video.
Let’s take a look at one edge of the tree. If this edge is removed, there are two sub-trees instead of the initial tree. Let’s assume that one of these sub-trees contains x vertices. Then there’re exactly y = n — x vertices in another sub-tree. There’re at most 2 * min(x, y) paths going through this edge. So all we need to know is how many vertices there are in each of two sub-trees if this edge is removed. (For edge i, let it be x[i] and y[i]) It’s clear that the answer is the sum for all edges: 2 * min(x[i], y[i]) * weight[i] (weight[i] — weight of the i-th edge).

Now all that is left for us is to compute x[i] and y[i] that is the number of vertices in each subtree for every edge. We can compute this using DFS and hence solve the problem.

For your DFS function , follow these steps.

  1. Make a boolean array “visited” and an integer array “count”. Both of size V , no of vertices. Initialise both to 0.
  2. Make an ans=0 variable and pass it to DFSHelper function by reference.
  3. Make the call to DFSHelper function passing all the required arguments.
  4. Print the modified value of ans variable.

For the DFSHelper function , follow these steps.
( This is a recursive function )
dfsHelper ( visited[] , count[] , &ans , currentNode )

  1. Mark the current node as visited in visited array.
  2. Mark its count as 1.
  3. Iterate over its neighbours and check if any neighbour is unvisited.
  4. If so, make a recursive call over that neighbour node and add its count ( the result returned from it ) to the count of current node.
  5. Add its contribution to the final ans as
    ans += 2*min( count[v] , N - count[v] ) * edgeWeight ;
    where v is the neighbour , N is the total vertices count.
  6. After all iterations are done , return count[currentNode] .
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.