题目详情 - L2-043 龙龙送外卖 (pintia.cn)
这题题目不好理解。
思路：由于最后不用返回外卖点，通过手动模拟最短路径可以发现贪心策略就是：在最大深度那里不要返回会使总距离最小，而其他点都需要计算返回到上个访问到的点或根节点的两倍距离。那么答案就是：总距离-最大深度。
每次添加订单都可能会导致这里的最大深度发生变化，所以这里就有点像dp。
#include<iostream>
using namespace std;
const int N = 100010;
int t[N], dis[N], maxl, root = -1;
int dfs(int x,int d){
if(t[x] == -1 || dis[x]){//根节点或当前结点已经访问过
maxl = max(maxl,d+dis[x]);
return d*2;
}
int res = dfs(t[x],d+1);
dis[x] = dis[t[x]] + 1;
return res;
}
int main(){
cin.tie(0)->sync_with_stdio(false); cout.tie(0);
int n,m; cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>t[i];
int sum = 0;
while(m--){
int x; cin>>x;
sum += dfs(x,0);
cout<<sum-maxl<<endl;
}
return 0;
} 
