➤ Problem Link : 682C. Alyona and the Tree
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int n;
int ans=0;
ll sz[100002];
ll arr[100002];
vector<pair<int,ll> > adj[100002];
#define mp make_pair
#define pb push_back
int calcSize(int v, int p)
{
sz[v]=1;
if(p!=-1 && adj[v].size()==1)
return 1;
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i].first==p)
continue;
sz[v]+=calcSize(adj[v][i].first, v);
}
return sz[v];
}
void dfs(int v,int p, ll mxval)
{
if(mxval > arr[v])
{
ans+=sz[v];
return;
}
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i].first==p)
continue;
ll curr=max(adj[v][i].second,mxval+adj[v][i].second);
dfs(adj[v][i].first,v,curr);
}
}
int main()
{
int p;
ll c;
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int i=1;i<n;i++)
{
cin>>p>>c;
adj[i+1].pb(mp(p,c));
adj[p].pb(mp(i+1,c));
}
memset(sz,0,sizeof(sz));
calcSize(1,-1);
// cout<<sz[1]<<endl;
dfs(1,-1,(ll)-1*pow(10,9));
cout<<ans;
}
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!!
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.