➤ Problem Link : 743D. Chloe and pleasant prizes
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ans;
pair<ll,ll> dfs(int v, ll arr[], vector<int> adj[],int p)
{
if(adj[v].size()==1 && p!=-1)
{
return make_pair(arr[v],arr[v]);
}
ll mx=LONG_MIN,sx=LONG_MIN;
ll sum=0;
pair<ll,ll> val;
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
val=dfs(adj[v][i],arr,adj,v);
sum+=val.first;
if(val.second>mx)
{
sx=mx;
mx=val.second;
}
else if(val.second>sx)
sx=val.second;
}
if(sx!=LONG_MIN && mx!=LONG_MIN)
ans=max(ans,sx+mx);
mx=max(mx,sum+arr[v]);
return make_pair(sum+arr[v],mx);
}
int main()
{
ans=LONG_MIN;
int n,u,v;
cin>>n;
ll arr[n+1];
vector<int> adj[n+1];
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int i=0;i<n-1;i++)
{
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,arr,adj,-1);
if(ans==LONG_MIN)
cout<<"Impossible";
else
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.