Given an N-array tree of N nodes, rooted at 1, with edges in the form {u, v}, and an array values[] consisting of N integers. Each vertex i has an integer value denoted by values[i]. The task is to find the largest Subtree Sum possible for each vertex i by adding its value to a non-empty subset of its child vertices.
Examples:Â
Input: Edges[][] = {{1, 2}, {1, 3}, {3, 4}}, values[] = {1, -1, 0, 1}
Output: 2 -1 1 1
Explanation:
Below is the given Tree:Â Â Â Â Â Â Â Â Â Â Â Â Â 1
            /  \
           2   3
               \
                4
Following subsets can be chosen for each vertex:
Vertex 1: Subset of vertices {1, 3, 4} can be chosen with values {1, 0, 1}. Therefore, sum = 1 + 0 + 1 = 2.
Vertex 2: Subset of vertices {2} can be chosen with values {-1}. Therefore, sum = -1.
Vertex 3: Subset of vertices {3, 4} can be chosen with values {0, 1}. Therefore, sum = 0 + 1 = 1.
Vertex 4: Subset of vertices {4} can be chosen with values {1}. Therefore, sum = 1.Input: Edges[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}, values[] = {1, -1, -2, 1, 3}
Output: 5 4 -2 1 3
Explanation:
Below is the given Tree:Â Â Â Â Â Â Â Â Â Â Â Â Â 1
            /  \
           2   3
         /  \  Â
        4    5
Following subsets can be chosen for each vertex:
Vertex 1: Subset of vertices {1, 4, 5} can be chosen with values {1, 1, 3}. Therefore, sum = 1 + 1 + 3 = 5.
Vertex 2: Subset of vertices {4, 5} can be chosen with values {1, 3}. Therefore, sum = 1 + 3 = 4.Â
Vertex 3: Subset of vertices {3} can be chosen with values {-2}. Therefore, sum = -2.
Vertex 4: Subset of vertices {4} can be chosen with values {1}. Therefore, sum = 1.
Vertex 5: Subset of vertices {5} can be chosen with values {3}. Therefore, sum = 3.Â
Naive Approach: The simplest approach is to traverse the subtree of each vertex i from 1 to N and perform DFS Traversal on it. For each vertex i, choose the subset of its child vertices having non-negative values. If the subset of chosen vertices is empty, then search and print the node having the minimum value such that it is the child node of vertex i. Otherwise, print the sum of node values of nodes present in the subset.Â
Time Complexity: O(N2)
Auxiliary Space: O(N)Â
Efficient Approach: The idea is to use DFS Traversal and Dynamic programming approach. Follow the below steps to solve the problem:
- Initialize an array ans[] of size N to store the maximum subtree sum for each vertex.
- Perform DFS Traversal for each vertex and for each vertex initialize v, ans[v] with some large negative value.
- If vertex v is a leaf vertex, then the answer for that vertex would be values[v]. Therefore, assign ans[v] = values[v].
- Otherwise, traverse the vertices adjacent to vertex v and for each adjacent vertex u, update ans[v] as ans[v] = max(ans[u] + values[v], values[v], ans[u]).
- After the above steps, print the values stored in ans[] array as the answer for each vertex.
Below is the implementation of the above approach:Â
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define V 3#define M 2Â
// Function to perform the DFS// Traversal on the given Treevoid dfs(int v, int p,         vector<int> adj[],     int ans[], int vals[]){         // To check if v is leaf vertex    bool isLeaf = 1;Â
    // Initialize answer for vertex v    ans[v] = INT_MIN;Â
    // Traverse adjacency list of v    for(int u : adj[v])     {        if (u == p)            continue;                     isLeaf = 0;        dfs(u, v, adj, ans, vals);Â
        // Update maximum subtree sum        ans[v] = max(ans[u] + vals[v],                 max(ans[u], vals[u]));    }Â
    // If v is leaf    if (isLeaf)     {        ans[v] = vals[v];    }}Â
// Function to calculate maximum// subtree sum for each vertexvoid printAnswer(int n,                  int edges[V][M],                 int values[]){         // Stores the adjacency list    vector<int> adj[n];         // Add Edges to the list    for(int i = 0; i < n - 1; i++)     {        int u = edges[i][0] - 1;        int v = edges[i][1] - 1;                 adj[u].push_back(v);        adj[v].push_back(u);    }Â
    // Stores largest subtree    // sum for each vertex    int ans[n] ;Â
    // Calculate answer    dfs(0, -1, adj, ans, values);Â
    // Print the result    for(auto x : ans)     {        cout << x << " ";    }}Â
// Driver Codeint main(){         // Given nodes    int N = 4;Â
    // Give N edges    int edges[V][M] = { { 1, 2 },                        { 1, 3 },                        { 3, 4 } };Â
    // Given values    int values[] = { 1, -1, 0, 1 };Â
    // Function Call    printAnswer(N, edges, values);}Â
// This code is contributed by Princi Singh |
Java
// Java program for the above approachÂ
import java.io.*;import java.util.ArrayList;Â
@SuppressWarnings("unchecked")class GFG {Â
    // Function to perform the DFS    // Traversal on the given Tree    static void dfs(int v, int p,                    ArrayList<Integer> adj[],                    int ans[], int vals[])    {Â
        // To check if v is leaf vertex        boolean isLeaf = true;Â
        // Initialize answer for vertex v        ans[v] = Integer.MIN_VALUE;Â
        // Traverse adjacency list of v        for (int u : adj[v]) {            if (u == p)                continue;            isLeaf = false;            dfs(u, v, adj, ans, vals);Â
            // Update maximum subtree sum            ans[v] = Math.max(                ans[u] + vals[v],                Math.max(ans[u],                         vals[u]));        }Â
        // If v is leaf        if (isLeaf) {            ans[v] = vals[v];        }    }Â
    // Function to calculate maximum    // subtree sum for each vertex    static void printAnswer(        int n, int edges[][], int values[])    {Â
        // Stores the adjacency list        ArrayList<Integer> adj[]            = new ArrayList[n];Â
        for (int i = 0; i < n; i++)            adj[i] = new ArrayList<>();Â
        // Add Edges to the list        for (int i = 0; i < n - 1; i++) {Â
            int u = edges[i][0] - 1;            int v = edges[i][1] - 1;            adj[u].add(v);            adj[v].add(u);        }Â
        // Stores largest subtree        // sum for each vertex        int ans[] = new int[n];Â
        // Calculate answer        dfs(0, -1, adj, ans, values);Â
        // Print the result        for (int x : ans) {            System.out.print(x + " ");        }    }Â
    // Driver Code    public static void main(String[] args)    {        // Given nodes        int N = 4;Â
        // Give N edges        int edges[][]            = new int[][] { { 1, 2 },                            { 1, 3 },                            { 3, 4 } };Â
        // Given values        int values[] = { 1, -1, 0, 1 };Â
        // Function Call        printAnswer(N, edges, values);    }} |
Python3
# Python3 program for the above approachÂ
V = 3M = 2Â
# Function to perform the DFS# Traversal on the given Treedef dfs(v, p):Â
    # To check if v is leaf vertex    isLeaf = 1Â
    # Initialize answer for vertex v    ans[v] = -10**9Â
    # Traverse adjacency list of v    for u in adj[v]:        if (u == p):            continueÂ
        isLeaf = 0        dfs(u, v)Â
        # Update maximum subtree sum        ans[v] = max(ans[u] + vals[v],max(ans[u], vals[u]))Â
    # If v is leaf    if (isLeaf):        ans[v] = vals[v]Â
# Function to calculate maximum# subtree sum for each vertexdef printAnswer(n, edges, vals):Â
    # Stores the adjacency list    # vector<int> adj[n];Â
    # Add Edges to the list    for i in range(n - 1):        u = edges[i][0] - 1        v = edges[i][1] - 1Â
        adj[u].append(v)        adj[v].append(u)Â
    # Calculate answer    dfs(0, -1)Â
    # Print the result    for x in ans:        print(x, end=" ")Â
# Driver Codeif __name__ == '__main__':Â
    # Given nodes    N = 4Â
    # Give N edges    edges=[ [ 1, 2],            [ 1, 3],            [ 3, 4] ]Â
    adj=[[] for i in range(N)]    ans=[0 for i in range(N)]Â
    # Given values    vals=[1, -1, 0, 1]Â
    # Function Call    printAnswer(N, edges, vals)Â
# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{Â
// Function to perform the DFS// Traversal on the given Treestatic void dfs(int v, int p,                List<int> []adj,                int []ans, int []vals){  // To check if v is leaf   // vertex  bool isLeaf = true;Â
  // Initialize answer for  // vertex v  ans[v] = int.MinValue;Â
  // Traverse adjacency list  // of v  foreach (int u in adj[v])   {    if (u == p)      continue;    isLeaf = false;    dfs(u, v, adj, ans, vals);Â
    // Update maximum subtree     // sum    ans[v] = Math.Max(ans[u] +                      vals[v],             Math.Max(ans[u],                       vals[u]));  }Â
  // If v is leaf  if (isLeaf)  {    ans[v] = vals[v];  }}Â
// Function to calculate maximum// subtree sum for each vertexstatic void printAnswer(int n,                         int [,]edges,                         int []values){  // Stores the adjacency list  List<int> []adj =        new List<int>[n];Â
  for (int i = 0; i < n; i++)    adj[i] = new List<int>();Â
  // Add Edges to the list  for (int i = 0;            i < n - 1; i++)   {    int u = edges[i, 0] - 1;    int v = edges[i, 1] - 1;    adj[u].Add(v);    adj[v].Add(u);  }Â
  // Stores largest subtree  // sum for each vertex  int []ans = new int[n];Â
  // Calculate answer  dfs(0, -1, adj,       ans, values);Â
  // Print the result  foreach (int x in ans)   {    Console.Write(x + " ");  }}Â
// Driver Codepublic static void Main(String[] args){  // Given nodes  int N = 4;Â
  // Give N edges  int [,]edges = new int[,] {{1, 2},                             {1, 3},                             {3, 4}};  // Given values  int []values = {1, -1, 0, 1};Â
  // Function Call  printAnswer(N, edges, values);}}Â
// This code is contributed by gauravrajput1 |
Javascript
<script>Â
    // JavaScript program for the above approach         // Function to perform the DFS    // Traversal on the given Tree    function dfs(v, p, adj, ans, vals)    {      // To check if v is leaf      // vertex      let isLeaf = true;Â
      // Initialize answer for      // vertex v      ans[v] = Number.MIN_VALUE;Â
      // Traverse adjacency list      // of v      for(let u = 0; u < adj[v].length; u++)      {        if (adj[v][u] == p)          continue;        isLeaf = false;        dfs(adj[v][u], v, adj, ans, vals);Â
        // Update maximum subtree        // sum        ans[v] = Math.max(ans[adj[v][u]] +                          vals[v],                 Math.max(ans[adj[v][u]],                          vals[adj[v][u]]));      }Â
      // If v is leaf      if (isLeaf)      {        ans[v] = vals[v];      }    }Â
    // Function to calculate maximum    // subtree sum for each vertex    function printAnswer(n, edges, values)    {      // Stores the adjacency list      let adj = new Array(n);Â
      for (let i = 0; i < n; i++)        adj[i] = [];Â
      // Add Edges to the list      for (let i = 0; i < n - 1; i++)      {        let u = edges[i][0] - 1;        let v = edges[i][1] - 1;        adj[u].push(v);        adj[v].push(u);      }Â
      // Stores largest subtree      // sum for each vertex      let ans = new Array(n);Â
      // Calculate answer      dfs(0, -1, adj, ans, values);Â
      // Print the result      for(let x = 0; x < ans.length; x++)      {        document.write(ans[x] + " ");      }    }         // Given nodes    let N = 4;Â
    // Give N edges    let edges = [[1, 2], [1, 3], [3, 4]];    // Given values    let values = [1, -1, 0, 1];Â
    // Function Call    printAnswer(N, edges, values);Â
</script> |
Output:Â
2 -1 1 1
Â
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/largest-subtree-sum-for-each-vertex-of-given-n-ary-tree/ […]