class Solution {
public:
int second[100005];//bob访问节点的second[i]的时间
vector<int>node[100005];
bool dfs(int st,int fa,int end,int time)
{
second[st]=time;
if(st==end)
{
return true;
}
for(int i=0;i<node[st].size();i++)
{
int y=node[st][i];
if(y!=fa && dfs(y,st,end,time+1))
{
return true;
}
}
second[st]=-1;
return false;
}
int dfsValue(int st,int fa,int time,vector<int>& amount)
{
int value=0;
if(second[st]<time&&second[st]!=-1)
{
value=0;
}
else if(second[st]==time)
{
value=amount[st]/2;
}
else {
value=amount[st];
}
int sum=-1e9-5;
for(int i=0;i<node[st].size();i++)
{
int y=node[st][i];
if(y!=fa )
{
sum=max(sum,dfsValue(y,st,time+1,amount));
}
}
if(sum==-1e9-5) sum=0;
return value+sum;
}
int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
memset(second,-1,sizeof(second));
for(int i=0;i<edges.size();i++)
{
int x=edges[i][0];
int y=edges[i][1];
node[x].push_back(y);
node[y].push_back(x);
}
dfs(bob,-1,0,0);
// for(int i=0;i<amount.size();i++){
// cout<<second[i]<<endl;
// }
int res=dfsValue(0,-1,0,amount);
return res;
}
};