GPLT天梯赛2022真题 L2-3 龙龙送外卖 (25 分)（图论 + 记忆化搜索）

本题没有传送门，就把题目写清楚吧。

碎碎念

在考场上这道题没想出来，真是寄了。一直在想LCA，然后想dfs，最短路。后面想利用树的性质，怎么都想不出。

思路

先考虑每个点都要走一次且回到起点的情况，那就是每个点往上走，每条边都要走两次。这个可以类比dfs的过程，每条边都要走到两次才能保证回到起点。

由于本题要求无需回到起点，所以用路程减去一个最大深度（最长的一条链）就是答案。

比如这个图，我要从起点1去 3 5 8 9送外卖，就可以选择以8或者9为终点，那么就是每个点往上走直到“会经过的点”的边的数量 * 2 - 最长的链，这就是答案。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5 + 9;

int fa[maxn],dep[maxn];
bitset<maxn> vis;//用于标记某点是否走过 

int d(int x)//记忆化搜索 
{
	if(fa[x] == -1)return 0;
	else if(dep[x])return dep[x];
	return dep[x] = d(fa[x]) + 1;
}

signed main()
{
	int N, M;cin >> N >> M;
	for(int i = 1;i <= N; ++ i)
	{
		int x;scanf("%lld", &x);
		fa[i] = x;
	}
	for(int i = 1;i <= N; ++ i)dep[i] = d(i);//获取每个点的深度 
	
	int ans = 0, maxd = 0;//maxd记录最大深度 
	while(M --)
	{
		int x;scanf("%lld", &x);
		maxd = max(maxd, dep[x]);//更新最大深度
		 
		while(fa[x] != -1 && !vis[x]) //从x点向上直到 根 或 已经走过的点 
		{
			vis[x] = 1;
			x = fa[x];
			ans += 2;
		}
		
		printf("%lld\n",ans - maxd);//输出答案 
	}
	return 0;
}