Google | OA Coding Questions and Solutions | Set - 16 | 2022

Question

Given a tree of "N" nodes rooted at node "1" : Find the subtree with maximum sum and output that maximum sum. (Note : A subtree rooted at node "x" consists of node "x" and all the descendants of node "x")

Input Format

Integer "N".....

"N-1" lines mentioning two integers "u" and "v" which means there is undirected edge between node "u" and node "v" in the tree...

"N" lines where there are "N" integers(A[i]) which mention the value of ith node...

Consider example tree :

In this tree the maximum possible subtree sum is rooted at node "5" and sum is(5+8+5)

Hence answer is : 18

Link to original problem for submitting : https://www.hackerrank.com/contests/desiqna-oa-practice-contest-00/challenges/kumar-k-loves-tree

Answer 1

C++ code solution : 



#include <bits/stdc++.h>
using namespace std ; 
typedef long long int ll ; 
vector <ll> value(200005,0);
vector <ll> parent(200005,0);
vector <ll> used(200005,0);
vector <ll> dp(200005,0);
vector <ll> G[200005];
ll global_max_sum = -1e18 ; 
void dfs(ll node,ll p){
    used[node] = 1 ; 
    for(auto neighbours : G[node]){
        if(used[neighbours]==0 && neighbours!=parent[node]){
            parent[neighbours] = node ; 
            dfs(neighbours,node);
        }
    }

    ll sum = value[node] ; 
    for(auto neighbours : G[node]){
        if(neighbours!=parent[node]){
            sum+=(dp[neighbours]);
        }
    }
    dp[node] = sum; 
    global_max_sum = max(global_max_sum,sum);
}
int main() {

    ll n;
    cin>>n ; 
    value.clear();
    ll i = 1 ; 
    while(i<=n-1){
        ll x,y ;
        cin>>x>>y ; 
        G[x].push_back(y);
        G[y].push_back(x);
        i++;
    }

    i = 1 ; 
    while(i<=n){
        cin>>value[i];
        i++;
    }
    parent[1] = -1;
    dfs(1,-1);
    cout<<global_max_sum ; 

    return 0 ; 
}