# 2467. Most Profitable Path in a Tree
###### tags: `Leetcode` `Medium` `Graph` `DFS` `Tree`
Link: https://leetcode.com/problems/most-profitable-path-in-a-tree/description/
## 思路
很典型的一道graph题
### 2DFS
alice从node 0到leaf node有很多路可以走 但是bob只有一条路可以走
因此我们可以先从node 0开始dfs 记录每个node的parent node(这样bob就可以顺着parent node往上走即可) 并且记录每个node和node 0的距离
然后顺着bob的路往上走 如果bob到一个点的距离<alice到这个点的的距离 那么这个点的amount在alice经过的时候就会变成0 如果bob到一个点的距离=alice到这个点的距离 那么这个点的amount在alice经过的时候alice只能拿到amount/2
更新完amount之后再从root开始做一遍dfs 就能找到答案
Q: **无向tree**做dfs怎么预防已经访问的节点再被访问？
A: 在dfs的时候传递currnode和parentnode(currnode的parent) 如果nextnode(currnode的neighbor)等于parentnode 就直接跳过
### 1DFS
参考[这里](https://leetcode.com/problems/most-profitable-path-in-a-tree/discuss/2807411/python-one-dfs)
从上至下遍历 每个点的```d0```(the distance from node ```0``` to node ```i```)我们肯定知道，```db```(distance from node ```i``` to node ```bob```)可以透过dfs自己的children知道
## Code
2DFS

class Solution {
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        List<List<Integer>> graph = new ArrayList<>();
        int n = edges.length+1;
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] edge:edges){
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        int[] par = new int[n];
        int[] time = new int[n];
        // calculate the dist from 0 to every other node and get the parent node of every node
        dfsFrom0(graph, 0, 0, 0, par, time);
        // get bob's path
        bobPath(bob, 0, par, time, amount);
        // find the maximum net income
        return dfs(graph, 0, 0, 0, amount);
    }
    public void bobPath(int bob, int dist, int[] par, int[] time, int[] amount){
        if(bob==0) return;
        if(dist<time[bob]) amount[bob] = 0;
        else if(dist==time[bob]) amount[bob]/=2;
        bobPath(par[bob], dist+1, par, time, amount);
    }
    public void dfsFrom0(List<List<Integer>> graph, int cur, int p, int dist, int[] par, int[] time){
        time[cur]=dist;
        par[cur]=p;
        for(int next:graph.get(cur)){
            if(next==p) continue;
            dfsFrom0(graph, next, cur, dist+1, par, time);
        }
    }
    public int dfs(List<List<Integer>> graph, int cur, int p, int curNet, int[] amount){
        int maxNet = Integer.MIN_VALUE;
        for(int next:graph.get(cur)){
            if(next==p) continue;
            maxNet = Math.max(maxNet, dfs(graph, next, cur, curNet, amount));
        }
        if(maxNet==Integer.MIN_VALUE) return amount[cur];
        else return maxNet+amount[cur];
    }
}

1DFS

class Solution {
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        List<List<Integer>> graph = new ArrayList<>();
        int n = edges.length+1;
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] edge:edges){
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        return dfs(graph, 0, 0, 0, bob, amount)[0];
    }
    public int[] dfs(List<List<Integer>> graph, int cur, int d0, int p, int bob, int[] amount){
        int maxChild = Integer.MIN_VALUE;
        int db = cur==bob?0:graph.size();
        for(int next:graph.get(cur)){
            if(next==p) continue;
            int[] tmp = dfs(graph, next, d0+1, cur, bob, amount);
            maxChild = Math.max(maxChild, tmp[0]);
            db = Math.min(db, tmp[1]+1);
        }
        int curAmount = amount[cur];
        if(db<d0) curAmount=0;
        else if(db==d0) curAmount/=2;
        //cur node is a leaf node
        if(maxChild==Integer.MIN_VALUE) return new int[]{curAmount, db};
        else return new int[]{curAmount+maxChild, db};
    }
}