SMUSpring天梯赛1

补题1:龙龙送外卖

题意:

做法：思维--遍历方式,从输入的点往外卖点遍历,或标记过的点。回溯的时候更新深度！

//到达了最后一个送货点之后不用返回根结点.那么之前到达的点都是要折返点,那么就最后才送最深点节点。
    //还有就是如果在去节点8点时候，途径了节点2,那么这个时候去节点2的路可以忽略，因为是顺路的。
    //一边读入一边遍历,从输入的点开始,往上走.直到到达外卖站或到达一个被标记过的点,停止.
    // 回溯的时候更新深度！！ 而且dfs不是void类型，要返回该次点增加的代价.并且要更新deepest.输出sum-deepest即可.

int n,q,s,ans=0,deepest=0;
int fa[100005],depth[100005];
unordered_map<int,bool> mark;
int dfs(int cur,int d){
    if(cur==s||mark[cur]){
        deepest=max(deepest,depth[cur]+d);
        return 2*d;
    }
    int res=0;                          //res
    res+=dfs(fa[cur],d+1);
    depth[cur]=depth[fa[cur]]+1;
    mark[cur]=1;
    deepest=max(deepest,depth[cur]);
    return res;
}
void solve(){                       //补7-11--龙龙送外卖--思维-遍历方式
    //到达了最后一个送货点之后不用返回根结点.那么之前到达的点都是要折返点,那么就最后才送最深点节点。
    //还有就是如果在去节点8点时候，途径了节点2,那么这个时候去节点2的路可以忽略，因为是顺路的。
    //一边读入一边遍历,从输入的点开始,往上走.直到到达外卖站或到达一个被标记过的点,停止.
    // 回溯的时候更新深度！！
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x==-1) s=i;
        else fa[i]=x;
    }
    while(q--){
        int x;
        cin>>x;
        ans+=dfs(x,0);
        cout<<ans-deepest<<endl;
    }
}