1098A. Sum in the tree - Codeforces Solution C++ ~ CodingWithArt

➤ 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!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.