9 weeks ago

John 910

Hyderabad

Question 1

Edge Strength

You are given a weighted tree with N nodes and N-1 edges.

E is defined as a summation F(i,j) for all 1 <= i < j <= N. Also, F(i,j) is equal to the maximum value of the edge that is present on the simple path between node i and j.

You are required to determine the value of E.

Example

Assumption

• N = 5
• Edges = [(1,2,4),(2,3,1),(1,4,6),(4,5,12)]

Approach

• F(1,2) = 4. Because there exists only f edge with weight 4 on simple path between node 1 and 2.
• F(1,3) = 4. Because there exists 2 edges with weight 1 and 4 on simple path between node 1 and 3. We will take the maximum weight edge.
• Similarly, F(1,4) = 6, F(1,5) = 12
• F(2,3) = 1, F(2,4) = 6, F(2,5) = 12.
• F(3,4) = 6, F(3,5) = 12.
• F(4,5) = 12.
• Hence E = 4+4+1+6+12+6+12 = 75

Function Description

Complete the solve() function. This function takes the following 2 parameters and returns the value of E.

• N : Represents the number of nodes in weighted tree
• Edges : Represents the edges in tree in the form of 3 space separated integers

Input Format:

Note: This is the input format you must use to provide custom input available above the Compile and Test button.

• The first line contains an integer N denoting the number of nodes in a tree.
• The next N-1 lines contain three space separated integers u, v and w denoting an edge between node u and v with weight w.

Output Format:

Print the required value of E.

Constraint:

• 1 <= N <= 2 * 10^5
• 1 <= w <= 10^5
• 1 <= u,v <= N

Sample Input

3
1  2  10
1  3  2

Sample Output

22

Explanation

Given

• N = 3
• Edges = [[1,2,10],[1,3,2]]

Approach

• F(1,2) = 10
• F(1,3) = 2
• F(2,3) = 10
• E = F(1,2)+F(1,3)+F(2,3) = 10+2+10 = 22

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Question 1

Analysis

The problem becomes much simpler if we try to change our perspective. Rather than trying to find the maximum edge for all paths, lets try to find the number of paths for which the maximum weighted edge is a particular edge. If we can find out the number of paths for each edge, then we can find the answer to the problem easily.

Lets try to add the edges in the order of increasing values. Now by the property of a tree, every edge connects two connected components such that there is no path that starts from one of the component and goes to the other without traversing this edge. Also since we are adding the edges in increasing order, the value of all the edges present in the tree so far is less than or equal to the value of the current edge. Thus, we can say that the current edge will be the maximum weighted edge for all the paths that start from one of the component and goes to the other. The number of such paths will simply be the product of the sizes of components involved (You need to pick exactly one node from each of the components). We can thus add the contribution of this edge into the ans. This technique is used in a wide variety of problems and is popularly known as Contribution Technique.

Implementation

Based on the above analysis, we can solve the problem simply by using a DSU(Disjoint Set Union). The steps involved are:

• Sort the edges based on their weights and keep adding the edges in increasing order of their weight.
• As we add an edge that connects two components A and B, we add W*|A|*|B|, where W is the weight of the current edge and |A| and |B| are the sizes of the components A and B respectively.

PseudoCode

class DSU:                                                       //DSU implemntation
    parent = [i for i in range(1,N)]
    size = [1]*N

    find(x):                                                     //find(x) returns the representative element of the set containing x
        return parent[x] = (parent[x] == x) ? x : find(parent[x])

    merge(a,b):                                                  //We return the product of sizes of components involved in the merge operation
        a = find(a)
        b = find(b)
        ret = size[a] * size[b]
        if(size[b] > size[a]) swap(a,b)
        size[a] += size[b]
        parent[b] = a 
        return ret

solve(N, Edges)
    d = DSU(N)
    Edges.sort(key = weight)                                     //sort the edges w.r.t their weight
    ans = 0
    for edge in edges:                                           //add the edges in increasing order of their weight
        ans += edge.weight * d.merge(edge.a, edge.b)             // add the contribution of current edge into the ans
    return ans