L2-043 龙龙送外卖

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e5 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f3f3f3f;
int h[N], e[M], ne[M], idx;
int depth[N], dad[N], st[N];
// 当前访问过的所有节点中的最大深度
// 当前访问过的节点的个数
int max_depth = 0, nodesize = 0;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
// 求解每个点的深度
void dfs(int u, int fa)
{
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int b = e[i];
        if(b == fa) continue;
        depth[b] = depth[u] + 1;
        dfs(b, u);
    }
}
//从u点向上搜索，并且标记访问的点
void up(int u)
{
    if(u == -1) return;
    if(st[u] == 1) return ;
    st[u] = 1;
    max_depth = max(max_depth, depth[u]);
    nodesize ++;
    up(dad[u]);
}
signed main()
{
    memset(h, -1, sizeof h);
    int n, m, root;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int fa;
        cin >> fa;
        dad[i] = fa;
        if(fa == -1)
        {
            root = i;
        }
        else
        {
            add(i, fa);
            add(fa, i);
        }
    }
    depth[root] = 0;
    dfs(root, -1);
    for(int i = 0; i < m; i ++)
    {
        int x;
        cin >> x;
        up(x);
        // (nodesize - 1) * 2:访问当前所有的送餐地址，需要访问的点的个数
        // max_depth：从起点到所有当前送餐地址中，最大的距离
        int res = (nodesize - 1) * 2 - max_depth;
        cout << res << endl;
    }
    return 0;
}