➤ Problem Link : 1098A. Sum in the tree
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; #define ll long long int vector<int> adj[100001]; ll sum[100001]; ll arr[100001]; bool flag; void func(int v, int psum) { int q; ll mini=LONG_MAX; for(int i=0;i<adj[v].size();i++) { q=adj[v][i]; mini=min(sum[q],mini); for(int j=0;j<adj[q].size();j++) func(adj[q][j],sum[q]); } if(adj[v].size()==0) { arr[v]=0; return; } if(psum>mini) { flag=1; return; } arr[v]=mini-psum; for(int i=0;i<adj[v].size();i++) { q=adj[v][i]; arr[q]=sum[q]-arr[v]-psum; } } int main() { int n,p; cin>>n; flag=0; for(int i=2;i<=n;i++) { cin>>p; adj[p].push_back(i); } for(int i=1;i<=n;i++) cin>>sum[i]; arr[1]=sum[1]; for(int i=0;i<adj[1].size();i++) func(adj[1][i],sum[1]); ll s=0; if(!flag) { for(int i=1;i<=n;i++) s+=arr[i]; cout<<s; } else cout<<"-1"; }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!