※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
: 　
: https://leetcode.com/problems/most-profitable-path-in-a-tree
: 2467. Most Profitable Path in a Tree
: 给你一个大小为n-1的阵列表示边，表示无向图的n个点，alice从0出发，bob从bob出发
: ，两者同时出发，他们会拿走每个点上面的分数，如果他们遇到了则会平分分数，alice
: 可以走到任意的叶子节点(不含0)，bob只能走到0，求出alice可能拿到的最大分数。
: 　
: 思路:
: 1.bob只能走到0，所以我们可以先找出bob走到0的路径中，走到每个点花的时间，用dfs
: 找就可以了，如果路径终点不为0，该点就标记成无限大。
: 2.alice用dfs遍历所有点，如果这个点bob比你早走过你就拿不到分数，如果你们同时到
: 就平分，如果你早到就全拿，当走到叶子节点的时候取最大的分数。
: 　
: 　
思路
一样
重点就是要知道bob有走过的地方
在那个地方他们两个人走了多远
就可以知道当前该0 1/2 或是1了
然后他们两个的dfs逻辑不太一样
所以分开来写
0.0
今天好麻烦
```cpp
class Solution {
public:
vector<int> passed;
vector<int> bobpassed;
unordered_map<int,int> bobmap;
unordered_map<int,vector<int>> path;
vector<int> amounts;
int res;
void bob(int now , int dist , vector<int>& sb)
{
sb.push_back(now);
if(now == 0)
{
for(int i = 0 ; i < sb.size() ; i ++)
{
bobmap[sb[i]] = i+1;
}
return ;
}
for(int nxt : path[now] )
{
if(bobpassed[nxt] == 1)continue;
bobpassed[nxt] = 1;
bob(nxt , dist+1 , sb);
}
sb.pop_back();
}
void alice(int now , int dist , int money)
{
if(bobmap[now] == dist)
{
money += amounts[now]/2;
}
else if(bobpassed[now] == 1 && bobmap[now] < dist)
{
}
else
{
money += amounts[now];
}
// cout << now << " " << money << " " << dist << endl;
if(path[now].size() == 1 && now != 0)
{
res = max(res,money);
return;
}
for(int nxt : path[now])
{
if(passed[nxt] == 1)continue;
passed[nxt] = 1;
alice(nxt , dist+1 , money);
}
}
int mostProfitablePath(vector<vector<int>>& edges, int bobh, vector<int>& am
ount)
{
res = INT_MIN;
int n = edges.size();
amounts = amount;
passed.resize(n+1,0);
bobpassed.resize(n+1,INT_MAX);
for(int i = 0 ; i <= n ; i ++)
{
bobmap[i] = INT_MAX;
}
for(int i = 0 ; i < n ; i ++)
{
path[edges[i][0]].push_back(edges[i][1]);
path[edges[i][1]].push_back(edges[i][0]);
}
vector<int> hi;
bobpassed[bobh] = 1;
bob(bobh , 1 , hi );
passed[0] = 1;
alice(0,1,0);
return res;
}
};
```