0 like 0 dislike
1,157 views

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)

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

edited | 1,157 views

0 like 0 dislike
```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 ;
}```

by Expert (110,880 points)