AcWing1024 -- 记忆化搜索 & 天梯赛

1. 题目描述

2022年天梯赛正赛 \(DIV2\)

2. 思路

首先认真读题，题目说的是每次送完外卖之后不必返回起点。
另外，需要送外卖的点是逐个添加，每添加一次都要算一次最短路。

我们假设一次性把所有点都添加了，此时如何求最短路呢？
如果说我们可以一条路走到黑而无需回头走的话，那么此时最短路就是最深的那个点距离根的距离。
否则，例如样例中添加 \(5,6,2,3\) 之后，有多个分支，我们必须回头走，但是，有一个分支我们是不需要回头走的，还记得前面说的吗，“每次送完外卖之后不必返回起点。”。

出于贪心的角度，我们肯定希望不需要回头走的那个分支尽可能的长，这样我们少走的距离肯定更少。

因此，最短路就等于：走过的路径之和 * 2 - 最长的分支长度

好的，我们已经解决了如何找到答案，但是题目中的点不是一次性全部给出的啊，难道每给一个点我们都需要遍历一次树来查找路经之和以及最长的分支长度吗？其实是不必的，我们可以保存之前查找过的信息，下次搜索时直接使用，所谓“记忆化搜索”。

3. 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m, fa[N];
int sum;    // 保存走过的路经之和
int maxn;   // 保存走过的最长分支
int f[N];   // 保存某个节点到根节点的距离

// 返回 u 到根节点的路径长
// 求该长度的同时，我们便可以维护 sum 
int dfs(int u)
{
    // 如果是根节点或者已经搜索过了
    if(fa[u] == -1 || f[u] != -1) return f[u];
    // 走一步到父节点
    sum ++ ;
    // 记忆化
    return f[u] = 1 + dfs(fa[u]);
}

int main()
{
    // 因为根到根的距离为0，所以我们要将f设置为非-1的特殊值
    // 以方便我们判断某个点有没有走过
    memset(f, -1, sizeof f);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )  
    {
        cin >> fa[i];
        // root
        if(fa[i] == -1) f[i] = 0;
    }
    for(int i = 1; i <= m; i ++ )
    {
        int x;  cin >> x;
        // 对于每个点，我们查找它走过的路径之和
        // 注意这里需要去重
        // 另外，从根开始找路径是找不到的
        // 我们必须从当前节点往根遍历
        maxn = max(maxn, dfs(x));
        cout << sum * 2 - maxn << endl;
    }
    return 0;
}

4. 参考

Reference1