Given the edges of a tree and a sum S. The task is to assign weights to all the edges of the tree such that the longest path in terms of weights is minimized and the total sum of weights assigned should be S and print the longest path’s weight.
Note: Edges can be assigned any weights in range [0, S] and can be fractional also.
Examples:
Input:
1
/ | \
2 3 4
S = 3
Output: 2
All the edges can be assigned weights of 1, so
the longest path will in terms of weight will be
2--1--4 or 2--1--3
Input: 1
/
2
/ \
3 4
/ \
5 6
S = 1
Output: 0.50
Assign the given below weights to edges.
1--2: 0.25
2--3: 0.25
2--4: 0
4--5: 0.25
4--6: 0.25
Hence the longest path in terms of weight is 1--2--3
or 1--2--4--5 or 1--2--4--6.
Approach: The property of a tree that a path can have a maximum of two leaf nodes in it can be used to solve the above problem. So if we assign weights only to the edges connecting the leaf nodes, and assign other edges to 0. Then every edge connecting to the leaf nodes will be assigned s/(number of leaf nodes). Since a path can contain a maximum of two leaf nodes, hence the longest path will be 2 * (s/number of leaf nodes).
Step-by-step approach of the above idea:
- Define a function named addEdges which takes in two integers u and v, and an array adj[] as input.
- Add v to the uth index of the adj array and add u to the vth index of the adj array.
- Define a function named longestPath which takes in an array adj[], an integer s and an integer n as input.
- initialize a variable cnt to 0.
- Iterate through the array adj from index 1 to n. If the size of the array at index i is 1, increment the cnt variable by 1.
- Calculate the average weight of edges by dividing the given sum s by the number of leaf nodes (cnt).
- Multiply the average weight by 2 and assign the result to the variable ans.
- Return ans.
Below is the implementation of the above approach:
C++
// C++ program to assign weights to edges to// minimize the longest path in terms of weight#include <bits/stdc++.h>using namespace std;// Function to add edgesvoid addEdges(int u, int v, vector<int> adj[]){ adj[u].push_back(v); adj[v].push_back(u);}// Function that assigns weights// and returns the longest pathlong double longestPath(vector<int> adj[], int s, int n){ int cnt = 0; for (int i = 1; i <= n; i++) { if (adj[i].size() == 1) cnt++; } long double ans = 2.0 * (long double)(s / (long double)(cnt)); return ans;}// Driver Codeint main(){ int n = 4; // Create an adjacency list // to store tree vector<int> adj[n + 1]; // Add edges addEdges(1, 2, adj); addEdges(1, 3, adj); addEdges(1, 4, adj); // Given Sum int s = 3; // Function that prints the // longest path in terms of weights cout << longestPath(adj, s, n);} |
Java
// Java program to assign weights to edges to// minimize the longest path in terms of weightimport java.util.*;class GFG { // Function to add edges static void addEdges(int u, int v, Vector<Integer> adj[]) { adj[u].add(v); adj[v].add(u); } // Function that assigns weights // and returns the longest path static double longestPath(Vector<Integer> adj[], int s, int n) { int cnt = 0; for (int i = 1; i <= n; i++) { if (adj[i].size() == 1) cnt++; } double ans = 2.0 * (double) (s / (double) (cnt)); return ans; } // Driver Code public static void main(String[] args) { int n = 4; // Create an adjacency list // to store tree Vector<Integer>[] adj = new Vector[n + 1]; for (int i = 0; i < n + 1; i++) adj[i] = new Vector<Integer>(); // Add edges addEdges(1, 2, adj); addEdges(1, 3, adj); addEdges(1, 4, adj); // Given Sum int s = 3; // Function that prints the // longest path in terms of weights System.out.print(longestPath(adj, s, n)); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to assign weights to # edges to minimize the longest path # in terms of weight # Function to add edges def addEdges(u, v, adj): adj[u].append(v) adj[v].append(u) # Function that assigns weights # and returns the longest path def longestPath(adj, s, n): cnt = 0 for i in range(1, n + 1): if len(adj[i]) == 1: cnt += 1 ans = 2 * (s / cnt) return ans # Driver Code if __name__ == "__main__": n = 4 # Create an adjacency list # to store tree adj = [[] for i in range(n + 1)] # Add edges addEdges(1, 2, adj) addEdges(1, 3, adj) addEdges(1, 4, adj) # Given Sum s = 3 # Function that prints the # longest path in terms of weights print(longestPath(adj, s, n))# This code is contributed by Rituraj Jain |
C#
// C# program to assign weights to edges to// minimize the longest path in terms of weightusing System;using System.Collections.Generic;class GFG { // Function to add edges static void addEdges(int u, int v, List<int> []adj) { adj[u].Add(v); adj[v].Add(u); } // Function that assigns weights // and returns the longest path static double longestPath(List<int> []adj, int s, int n) { int cnt = 0; for (int i = 1; i <= n; i++) { if (adj[i].Count == 1) cnt++; } double ans = 2.0 * (double) (s / (double) (cnt)); return ans; } // Driver Code public static void Main(String[] args) { int n = 4; // Create an adjacency list // to store tree List<int>[] adj = new List<int>[n + 1]; for (int i = 0; i < n + 1; i++) adj[i] = new List<int>(); // Add edges addEdges(1, 2, adj); addEdges(1, 3, adj); addEdges(1, 4, adj); // Given Sum int s = 3; // Function that prints the // longest path in terms of weights Console.Write(longestPath(adj, s, n)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to assign weights to edges to// minimize the longest path in terms of weight// Function to add edgesfunction addEdges(u, v, adj){ adj[u].push(v); adj[v].push(u);}// Function that assigns weights// and returns the longest pathfunction longestPath(adj, s, n){ var cnt = 0; for (var i = 1; i <= n; i++) { if (adj[i].length == 1) cnt++; } var ans = 2.0 * (s / (cnt)); return ans;}// Driver Codevar n = 4;// Create an adjacency list// to store treevar adj = Array.from(Array(n+1), ()=>Array());// Add edgesaddEdges(1, 2, adj);addEdges(1, 3, adj);addEdges(1, 4, adj);// Given Sumvar s = 3;// Function that prints the// longest path in terms of weightsdocument.write( longestPath(adj, s, n));</script> |
Output
2
Complexity Analysis:
- Time Complexity: O(N), as we are using a loop to traverse N times, where N is the number of nodes in the tree.
- Auxiliary Space: O(N), as we are using extra space for adj array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
