AcWing 4474. 龙龙送外卖
原题链接
中等
作者:
Ac-Ciallo
,
2024-03-29 21:45:44
,
所有人可见
,
阅读 11
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N];//父节点
int d[N];//距离根的距离
int sum=0,mx;
//sum:距离总和,mx:最远点距离
int dfs(int u)
{
if(p[u]==-1||d[u]!=0) return d[u];
//根节点和已经确定距离的节点,不需要更新
sum++;
d[u]=dfs(p[u])+1;
return d[u];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
while(m--)
{
int x; cin>>x;
mx=max(mx,dfs(x));
cout<<(sum*2-mx)<<endl;
}
return 0;
}