PAT::L2_043::龙龙送外卖

Solution1：(DFS)

1. 本题贪心策略不难想到：即找到最长的路径不走回头路，最终总路径长度为：$2\times sum-max_l$，其中$sum$时连接各个树中各个结点需要的边的数量的最小值，$max_l$是树中所有结点中深度的最大值。
2. 关键是其中的sum如何计算、以及各个结点的深度如何计算；这道题也提供了计算树中各个结点深度的一个新方法（从孩子结点向上计算深度），同时也是1个模板：《遍历树中部分点需要的最少的边的数量》
3. 注意到结点都是1个1个输入的，我们可以将每次输入的结点看作叶子结点，用并查集的方法：对每个输入的向前溯源：不断找fa，并用fa的深度更新当前结点的深度。另一方面：sum等价于树中遍历过的边的数量，搜索时，仅在某个结点第1次被搜到时，sum++，其它情况下直接返回当前结点的深度做一个剪枝。
4. $max_l$的另一种求法：从根结点向下正向预处理出所有结点的深度，这样$max_l$可以随输入动态维护最大值。但是，我们要在输入的结点中找遍历所有这些结点的sum(即连接这些点需要用到边的数量)，这件事并不容易从根结点向下搜索求出，但从每次输入的新结点向上找父结点，并根据父结点是否搜索过决定剪枝还是递归就能很容易求出sum。（《连接全部给定的树上结点所需的最小的边的数量》）

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,m;
int f[N], d[N];
int sum, mx;        //sum记录到所有这些点边数之和，mx记录到根结点最远的距离

int dfs(int u)
{
    //记忆化搜索剪枝
    if(f[u] == -1 || d[u]) return d[u];
    //如果是第一次搜索到某个点
    sum++;
    d[u] = dfs(f[u])+1;
    return d[u];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i<=n; ++i) scanf("%d", &f[i]);
    while(m--){
        int x;
        scanf("%d", &x);
        mx = max(mx, dfs(x));      //从叶子结点向根结点计算，非常像并查集，但没有路径压缩
        printf("%d\n", sum*2-mx);
    }
    return 0;
}