Given a tree with N node and N-1 edges and an array arr[] where arr[i] denotes the value of ith node, the task is to find a set of nodes such that the sum of values is minimum and all the other nodes outside the set have an edge with at least one of the nodes in the set.
Examples:
Input: N = 3, edges[] = { {0, 1}, {1, 2} }, arr[] = { 5, 12, 3}
Output: 8
Explanation: We can select set {0, 2}, now unselected node {1} is connected to a selected node. Sum of values of subset nodes = A[0]+A[2] = 5+3 = 8Input: N = 4 edges[] = { {1, 0}, {3, 0}, {2, 3} }, A[] = { 3, 4, 20, 14}
Output: 17
Explanation: We can select subset {0, 3}. Now unselected node {1} has an edge with node {0} and unselected node{2} has an edge with node {3}. Sum of values of subset nodes = A[0] + A[3] = 3 + 14 = 17
Naive Approach: The problem can be solved based on the following idea:
For each node there are two choices – either to pick or not pick an element to be a part of the set.
Follow the steps mentioned below to implement the idea:
- Suppose we are at a given node x.
- Now if we include the current node x, then for its children we can either take its child or leave it.
- If we don’t include the current node x, then we have to include its children.
- Now start a dfs from any node (say 0).
- Initialize ans to 0.
- Maintain a variable (say pick) for a given dfs. which represents whether it is compulsory to pick the current node or there are options.
- If pick = 1, include the current node in the ans.
- If pick = 0, first calculate ans by taking the current node and then leaving it. Return the minimum of the two possible cases.
- Run the dfs from any start node.
- Return the value of ans.
Below is the Implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the subsetint dfs(int root, map<int, vector<int> >& graph, vector<int>& v, int pick, int parent){ int ans = 0; // Checking if it is compulsory // to pick the current element if (pick) { ans += v[root]; for (auto it : graph[root]) { if (it != parent) { ans += dfs(it, graph, v, 0, root); } } } // Two choices either pick or not pick an element else { int temp = v[root]; for (auto it : graph[root]) { if (it != parent) { temp += dfs(it, graph, v, 0, root); } } // If we leave the current element for (auto it : graph[root]) { if (it != parent) { ans += dfs(it, graph, v, 1, root); } } // ans stores the final ans ans = min(ans, temp); } // Return the final ans return ans;}// Function to find the minimum sumint findminSum(int edges[][2], vector<int>& v, int N){ map<int, vector<int> > graph; // Form the tree for (int i = 0; i < N - 1; i++) { int a = edges[i][1]; int b = edges[i][0]; graph[a].push_back(b); graph[b].push_back(a); } int pick = 0; int parent = -1; // Function call return dfs(0, graph, v, pick, parent);}// Driver Codeint main(){ // TestCase 1 int N = 4; vector<int> arr = { 3, 4, 20, 14 }; int edges[][2] = { { 1, 0 }, { 3, 0 }, { 2, 3 } }; cout << findminSum(edges, arr, N) << endl; // TestCase 2 int N2 = 3; vector<int> arr2 = { 5, 12, 3 }; int edges2[][2] = { { 0, 1 }, { 1, 2 } }; cout << findminSum(edges2, arr2, N2) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the subset public static int dfs(int root, Map<Integer, List<Integer> > graph, List<Integer> v, int pick, int parent) { int ans = 0; // Checking if it is compulsory // to pick the current element if (pick == 1) { ans += v.get(root); for (int it : graph.get(root)) { if (it != parent) { ans += dfs(it, graph, v, 0, root); } } } // Two choices either pick or not pick an element else { int temp = v.get(root); for (int it : graph.get(root)) { if (it != parent) { temp += dfs(it, graph, v, 0, root); } } // If we leave the current element for (int it : graph.get(root)) { if (it != parent) { ans += dfs(it, graph, v, 1, root); } } // ans stores the final ans ans = Math.min(ans, temp); } // Return the final ans return ans; } static int findminSum(int[][] edges, List<Integer> v, int N) { Map<Integer, List<Integer> > graph = new HashMap<>(); // Form the tree for (int i = 0; i < N - 1; i++) { int a = edges[i][1]; int b = edges[i][0]; if (!graph.containsKey(a)) { graph.put(a, new ArrayList<>()); } if (!graph.containsKey(b)) { graph.put(b, new ArrayList<>()); } graph.get(a).add(b); graph.get(b).add(a); } int pick = 0; int parent = -1; // Function call return dfs(0, graph, v, pick, parent); } public static void main(String[] args) { // TestCase 1 int N = 4; ArrayList<Integer> arr = new ArrayList<Integer>( Arrays.asList(3, 4, 20, 14)); int[][] edges = { { 1, 0 }, { 3, 0 }, { 2, 3 } }; System.out.println(findminSum(edges, arr, N)); // TestCase 2 int N2 = 3; ArrayList<Integer> arr2 = new ArrayList<Integer>( Arrays.asList(5, 12, 3)); int[][] edges2 = { { 0, 1 }, { 1, 2 } }; System.out.println(findminSum(edges2, arr2, N2)); }}// This code is contributed by lokeshmvs21. |
Python3
# python implementationdef dfs(root, graph, v, pick, parent): ans = 0 # Checking if it is compulsory # to pick the current element if pick: ans += v[root] for it in graph[root]: if it != parent: ans += dfs(it, graph, v, 0, root) # Two choices either pick or not pick an element else: temp = v[root] for it in graph[root]: if it != parent: temp += dfs(it, graph, v, 0, root) # If we leave the current element for it in graph[root]: if it != parent: ans += dfs(it, graph, v, 1, root) # ans stores the final ans ans = min(ans, temp) # Return the final ans return ansdef findminSum(edges, v, N): graph = {} # Form the tree for i in range(N-1): a = edges[i][1] b = edges[i][0] graph[a] = graph.get(a, []) + [b] graph[b] = graph.get(b, []) + [a] pick = 0 parent = -1 # Function call return dfs(0, graph, v, pick, parent)# TestCase 1N = 4arr = [3, 4, 20, 14]edges = [[1, 0], [3, 0], [2, 3]]print(findminSum(edges, arr, N))# TestCase 2N2 = 3arr2 = [5, 12, 3]edges2 = [[0, 1], [1, 2]]print(findminSum(edges2, arr2, N2))# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG{ // Function to find the subset public static int Dfs(int root, Dictionary<int, List<int>> graph, List<int> v, int pick, int parent) { int ans = 0; // Checking if it is compulsory // to pick the current element if (pick == 1) { ans += v[root]; foreach (int it in graph[root]) { if (it != parent) { ans += Dfs(it, graph, v, 0, root); } } } // Two choices either pick or not pick an element else { int temp = v[root]; foreach (int it in graph[root]) { if (it != parent) { temp += Dfs(it, graph, v, 0, root); } } // If we leave the current element foreach (int it in graph[root]) { if (it != parent) { ans += Dfs(it, graph, v, 1, root); } } // ans stores the final ans ans = Math.Min(ans, temp); } // Return the final ans return ans; } static int FindMinSum(int[][] edges, List<int> v, int N) { Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); // Form the tree for (int i = 0; i < N - 1; i++) { int a = edges[i][1]; int b = edges[i][0]; if (!graph.ContainsKey(a)) { graph[a] = new List<int>(); } if (!graph.ContainsKey(b)) { graph[b] = new List<int>(); } graph[a].Add(b); graph[b].Add(a); } int pick = 0; int parent = -1; // Function call return Dfs(0, graph, v, pick, parent); } static void Main(string[] args) { // TestCase 1 int N = 4; List<int> arr = new List<int>(new int[] { 3, 4, 20, 14 }); int[][] edges = new int[][] { new int[] { 1, 0 }, new int[] { 3, 0 }, new int[] { 2, 3 } }; Console.WriteLine(FindMinSum(edges, arr, N)); // TestCase 2 int N2 = 3; List<int> arr2 = new List<int>(new int[] { 5, 12, 3 }); int[][] edges2 = new int[][] { new int[] { 0, 1 }, new int[] { 1, 2 } }; Console.WriteLine(FindMinSum(edges2, arr2, N2)); }}// This code is contributed by lokeshpotta20. |
Javascript
// Function to find the subsetfunction dfs(root, graph, v, pick, parent) { let ans = 0; // Checking if it is compulsory // to pick the current element if (pick) { ans += v[root]; graph[root].forEach(it => { if (it !== parent) { ans += dfs(it, graph, v, 0, root); } }); } else { // Two choices either pick or not pick an element let temp = v[root]; graph[root].forEach(it => { if (it !== parent) { temp += dfs(it, graph, v, 0, root); } }); // If we leave the current element graph[root].forEach(it => { if (it !== parent) { ans += dfs(it, graph, v, 1, root); } }); // ans stores the final ans ans = Math.min(ans, temp); } // Return the final ans return ans;}// Function to find the minimum sumfunction findminSum(edges, v, N) { let graph = {}; // Form the tree for (let i = 0; i < N - 1; i++) { let a = edges[i][1], b = edges[i][0]; if (!graph[a]) graph[a] = []; if (!graph[b]) graph[b] = []; graph[a].push(b); graph[b].push(a); } let pick = 0, parent = -1; // Function call return dfs(0, graph, v, pick, parent);}// TestCase 1let N = 4;let arr = [3, 4, 20, 14];let edges = [[1, 0], [3, 0], [2, 3]];console.log(findminSum(edges, arr, N));// TestCase 2let N2 = 3;let arr2 = [5, 12, 3];let edges2 = [[0, 1], [1, 2]];console.log(findminSum(edges2, arr2, N2)); |
Output
17 8
Time complexity: O(2N)
Auxiliary space: O(N)
Efficient Approach: The problem can be solved using memoization based on the following idea:
From the above recursion it can be seen that the approach has some overlapping subproblems. Here each unique state can be represented using two variables – one for the index (say i) and the other for representing if the element is picked or not (say j).
Now, use this memoization in the above recursion to avoid repeated calculation of the same subproblem.
Below is the Implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp array to store repeated stateint dp[1000][2];// Function to find the subsetint dfs(int root, map<int, vector<int> >& graph, vector<int>& v, int pick, int parent){ int ans = 0; // Checking overlapping subproblems if (dp[root][pick] != -1) { return dp[root][pick]; } // If it is compulsory to take the current element if (pick) { ans += v[root]; for (auto it : graph[root]) { if (it != parent) { ans += dfs(it, graph, v, 0, root); } } return ans; } // Choice to pick or not pick the element else { int temp = v[root]; for (auto it : graph[root]) { if (it != parent) { temp += dfs(it, graph, v, 0, root); } } // If we leave the current element for (auto it : graph[root]) { if (it != parent) { ans += dfs(it, graph, v, 1, root); } } // ans stores the final ans ans = min(ans, temp); } // Store the ans and return the final ans return dp[root][pick] = ans;}// Function to find the minimum sumint findminSum(int edges[][2], vector<int>& v, int N){ map<int, vector<int> > graph; // Forming the tree for (int i = 0; i < N - 1; i++) { int a = edges[i][1]; int b = edges[i][0]; graph[a].push_back(b); graph[b].push_back(a); } // Initialize the dp array memset(dp, -1, sizeof(dp)); int pick = 0; int parent = -1; // Function call return dfs(0, graph, v, pick, parent);}// Driver Codeint main(){ // TestCase 1 int N = 4; vector<int> arr = { 3, 4, 20, 14 }; int edges[][2] = { { 1, 0 }, { 3, 0 }, { 2, 3 } }; cout << findminSum(edges, arr, N) << endl; // TestCase 2 int N2 = 3; vector<int> arr2 = { 5, 12, 3 }; int edges2[][2] = { { 0, 1 }, { 1, 2 } }; cout << findminSum(edges2, arr2, N2) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // dp array to store repeated state static int[][] dp = new int[1000][2]; // Function to find the subset static int dfs(int root, Map<Integer, List<Integer> > graph, List<Integer> v, int pick, int parent) { int ans = 0; // Checking overlapping subproblems if (dp[root][pick] != -1) { return dp[root][pick]; } // If it is compulsory to take the current element if (pick == 1) { ans += v.get(root); for (int it : graph.get(root)) { if (it != parent) { ans += dfs(it, graph, v, 0, root); } } return ans; } // Choice to pick or not pick the element else { int temp = v.get(root); for (int it : graph.get(root)) { if (it != parent) { temp += dfs(it, graph, v, 0, root); } } // If we leave the current element for (int it : graph.get(root)) { if (it != parent) { ans += dfs(it, graph, v, 1, root); } } // ans stores the final ans ans = Math.min(ans, temp); } // Store the ans and return the final ans dp[root][pick] = ans; return ans; } // Function to find the minimum sum static int findminSum(int[][] edges, List<Integer> v, int N) { Map<Integer, List<Integer> > graph = new HashMap<>(); // Forming the tree for (int i = 0; i < N - 1; i++) { int a = edges[i][1]; int b = edges[i][0]; if (!graph.containsKey(a)) { graph.put(a, new ArrayList<>()); } graph.get(a).add(b); if (!graph.containsKey(b)) { graph.put(b, new ArrayList<>()); } graph.get(b).add(a); } // Initialize the dp array for (int i = 0; i < 1000; i++) { Arrays.fill(dp[i], -1); } int pick = 0; int parent = -1; // Function call return dfs(0, graph, v, pick, parent); } public static void main(String[] args) { // TestCase 1 int N = 4; List<Integer> arr = Arrays.asList(3, 4, 20, 14); int[][] edges = { { 1, 0 }, { 3, 0 }, { 2, 3 } }; System.out.println(findminSum(edges, arr, N)); // TestCase 2 int N2 = 3; List<Integer> arr2 = Arrays.asList(5, 12, 3); int[][] edges2 = { { 0, 1 }, { 1, 2 } }; System.out.println(findminSum(edges2, arr2, N2)); }}// This code is contributed by lokesh. |
Python3
# Python code to implement the approachfrom collections import defaultdict# dp array to store repeated statedp = [[-1 for _ in range(2)] for _ in range(1000)]# Function to find the subsetdef dfs(root, graph, v, pick, parent): ans = 0 # Checking overlapping subproblems if dp[root][pick] != -1: return dp[root][pick] # If it is compulsory to take the current element if pick: ans += v[root] for it in graph[root]: if it != parent: ans += dfs(it, graph, v, 0, root) return ans # Choice to pick or not pick the element else: temp = v[root] for it in graph[root]: if it != parent: temp += dfs(it, graph, v, 0, root) # If we leave the current element for it in graph[root]: if it != parent: ans += dfs(it, graph, v, 1, root) # ans stores the final ans ans = min(ans, temp) # Store the ans and return the final ans dp[root][pick] = ans return ans# Function to find the minimum sumdef findminSum(edges, v, N): graph = defaultdict(list) # Forming the tree for i in range(N-1): a, b = edges[i] graph[a].append(b) graph[b].append(a) pick = 0 parent = -1 # Function call return dfs(0, graph, v, pick, parent)# Driver Codeif __name__ == "__main__": # TestCase 1 N = 4 arr = [3, 4, 20, 14] edges = [[1, 0], [3, 0], [2, 3]] print(findminSum(edges, arr, N)) # TestCase 2 dp = [[-1 for _ in range(2)] for _ in range(1000)] N2 = 3 arr2 = [5, 12, 3] edges2 = [[0, 1], [1, 2]] print(findminSum(edges2, arr2, N2))# This code is contributed by Vikram_Shirsat |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // dp array to store repeated state static int[, ] dp = new int[1000, 2]; // Function to find the subset static int dfs(int root, Dictionary<int, List<int> > graph, List<int> v, int pick, int parent) { int ans = 0; // Checking overlapping subproblems if (dp[root, pick] != -1) { return dp[root, pick]; } // If it is compulsory to take the current element if (pick == 1) { ans += v[root]; foreach(int it in graph[root]) { if (it != parent) { ans += dfs(it, graph, v, 0, root); } } return ans; } // Choice to pick or not pick the element else { int temp = v[root]; foreach(int it in graph[root]) { if (it != parent) { temp += dfs(it, graph, v, 0, root); } } // If we leave the current element for (int it = 0; it < graph[root].Count; it++) { if (graph[root][it] != parent) { ans += dfs(graph[root][it], graph, v, 1, root); } } // ans stores the final ans ans = Math.Min(ans, temp); } // Store the ans and return the final ans dp[root, pick] = ans; return ans; } // Function to find the minimum sum static int findminSum(int[, ] edges, List<int> v, int N) { Dictionary<int, List<int> > graph = new Dictionary<int, List<int> >(); // Forming the tree for (int i = 0; i < N - 1; i++) { int a = edges[i, 1]; int b = edges[i, 0]; if (!graph.ContainsKey(a)) { graph.Add(a, new List<int>()); } graph[a].Add(b); if (!graph.ContainsKey(b)) { graph.Add(b, new List<int>()); } graph[b].Add(a); } // Initialize the dp array for (int i = 0; i < 1000; i++) { dp[i, 0] = -1; dp[i, 1] = -1; } int pick = 0; int parent = -1; // Function call return dfs(0, graph, v, pick, parent); } static public void Main() { // Code // TestCase 1 int N = 4; List<int> arr = new List<int>(new int[] { 3, 4, 20, 14 }); int[, ] edges = { { 1, 0 }, { 3, 0 }, { 2, 3 } }; Console.WriteLine(findminSum(edges, arr, N)); // TestCase 2 int N2 = 3; List<int> arr2 = new List<int>(new int[] { 5, 12, 3 }); int[, ] edges2 = { { 0, 1 }, { 1, 2 } }; Console.WriteLine(findminSum(edges2, arr2, N2)); }}// This code is contributed by karthik. |
Javascript
// JavaScript code to implement the approach// Function to find the subsetfunction dfs(root, graph, v, pick, parent, dp) { let ans = 0; // Checking overlapping subproblems if (dp[root][pick] != -1) { return dp[root][pick]; } // If it is compulsory to take the current element if (pick == 1) { ans += v[root]; for (let i = 0; i < graph[root].length; i++) { let it = graph[root][i]; if (it != parent) { ans += dfs(it, graph, v, 0, root, dp); } } return ans; } // Choice to pick or not pick the element else { let temp = v[root]; for (let i = 0; i < graph[root].length; i++) { let it = graph[root][i]; if (it != parent) { temp += dfs(it, graph, v, 0, root, dp); } } // If we leave the current element for (let i = 0; i < graph[root].length; i++) { let it = graph[root][i]; if (it != parent) { ans += dfs(it, graph, v, 1, root, dp); } } // ans stores the final ans ans = Math.min(ans, temp); } // Store the ans and return the final ans dp[root][pick] = ans; return ans;}// Function to find the minimum sumfunction findminSum(edges, v, N) { let graph = {}; // Forming the tree for (let i = 0; i < N - 1; i++) { let a = edges[i][1]; let b = edges[i][0]; if (!graph.hasOwnProperty(a)) { graph[a] = []; } graph[a].push(b); if (!graph.hasOwnProperty(b)) { graph[b] = []; } graph[b].push(a); } // Initialize the dp array let dp = new Array(1000).fill(-1).map(() => new Array(2).fill(-1)); let pick = 0; let parent = -1; // Function call return dfs(0, graph, v, pick, parent, dp);}// Test Caseslet N = 4;let arr = [3, 4, 20, 14];let edges = [[1, 0], [3, 0], [2, 3]];console.log(findminSum(edges, arr, N));let N2 = 3;let arr2 = [5, 12, 3];let edges2 = [[0, 1], [1, 2]];console.log("<br>" + findminSum(edges2, arr2, N2));// This code is contributed by sankar |
Output
17 8
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
