Most Profitable Path in a Tree | Leetcode 2467

This video explains Most Profitable Path in a Tree using the optimal DFS recursion and backtracking approach.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
---------------------------------------------------------------------------------------------------------------------------------------------------------------

[Sirpi-ir]

I misunderstood the question and it couldn't be explained any better than this. as always great video bro. 🔥

[chayaoswal]

Sir kindly upload videos by morning itself so that we can start our day by this because as working professional it is very difficult to solve by night

[freecourseplatformenglish]

😉❤. Took me an hour to code. Intution is not hard.
My approach
Step 1. construct a nodeMoveMap (moves taken by bob to reach a node) for Bob.
Step 2. Find the optimum path to leaf from 0 using nodeMoveMap.

[sudhanshukushwaha]

For the 'bob' path, can I move only to nodes with values less than the current node?

[uttamrawat]

First graph question which i feel tricky and i am using different approach and doesn't consider that there is only path exists for bob to reach at node 0. LOL

[sabiruddinkhan]

THANK YOU SIR
SOLUTION CODE :
class Solution {
public:
void Alice(int node, int parent, int sum, int&ans, vector<int>&amount, vector<int> adj[]){
sum+=amount[node];
bool check=false;
for(int i=0;i<adj[node].size();i++){
if(adj[node][i]!=parent){
check=true;
Alice(adj[node][i], node, sum, ans, amount, adj);
}
}
if(!check)
ans=max(ans, sum);
}
bool DFS(int node, int parent, vector<int>&bob_path, vector<int> adj[]){
if(node==0){
return 1;
}
for(int i=0;i<adj[node].size();i++){
if(adj[node][i]!=parent){
if(DFS(adj[node][i], node, bob_path, adj)){
bob_path.push_back(node);
return 1;
}
}
}
return 0;
}
int edges, int bob, vector<int>& amount) {
vector<int> adj[edges.size()+1];
for(int i=0;i<edges.size();i++){
int u=edges[i][0];
int v=edges[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int>bob_path;
DFS(bob, -1, bob_path, adj);
int k=bob_path.size()/2;
for(int i=k;i<bob_path.size();i++){
amount[bob_path[i]]=0;
}
if(bob_path.size()%2==0){
amount[bob_path[k-1]]/=2;
}
int ans=INT_MIN, sum=0;
Alice(0, -1, sum, ans, amount, adj);
return ans;
}
};