题目描述

帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。

看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？

每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。

为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 1
，且从外卖站出发可以访问到所有地点。

注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。

对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。

思路

先链式前向星存储，然后dfs得到所有点到根节点的距离。最后对于每个要去的点，累计统计一共走过了多少距离(sum)和最长距离(maxn)。

代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e5 + 5;
int h[N], e[N], ne[N], idx;
int p[N], dist[N]; // 父节点，距离 
bool st[N]; // 后续遍历时检查是否走过 
int n, m;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dist[j] = dist[u] + 1;
        dfs(j);
    }
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;

    int root;
    for(int i = 1; i <= n; ++i){
        cin >> p[i];
        if(p[i] == -1) root = i;
        else add(p[i], i);
    }

    dfs(root); // 获取所有点到根节点的距离

    int sum = 0, maxn = 0; // 总共走的路径长度和最大长度 
    while(m --){
        int x; cin >> x;
        maxn = max(maxn, dist[x]);
        while(!st[x] && x != root){ // 从这个点开始往上找 
            st[x] = true;
            sum ++;
            x = p[x];
        }
        cout << 2 * sum - maxn <<'\n';
    }
    return 0;
}

参考文献

https://www.cnblogs.com/MarisaMagic/p/17338796.html