BENEFACT - The Benefactor - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : BENEFACT

👉 Hint : Use DFS Algorithm and perform work while going up

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int,int> >adj[500001];
bool visited[500001];
int ans=-1;
int dfs(int v)
{
    visited[v]=1;
    vector<int>s;
    for(auto it=adj[v].begin();it!=adj[v].end();it++)
    {
        int vtx=(*it).first;
        if(!visited[vtx])
        {
            int l=(*it).second;
            int f=dfs(vtx);
            s.push_back(f+l);
        }
    }
    sort(s.begin(),s.end(),greater<int>());
    if(s.size()==0)
    {
        return 0;
    }
    if(s.size()==1)
    {
        int l1=s[0];
        if(l1>ans)
            ans=l1;
    }
    else
    {
    int l1=s[0]+s[1];
    if(l1>ans)
        ans=l1;
    }
    return s[0];
}
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        
        memset(visited,0,sizeof(visited));
        int n,x,y,v;
        cin>>n;
        for(int i=0;i<=n;i++)
            adj[i].clear();
        for(int i=1;i<n;i++)
        {
            cin>>x>>y>>v;
            adj[x].push_back(make_pair(y,v));
            adj[y].push_back(make_pair(x,v));
        }
        int f=dfs(1);
        cout<<ans<<endl;
        ans=-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.