L2-043 龙龙送外卖-Toy模板网

这篇具有很好参考价值的文章主要介绍了L2-043 龙龙送外卖。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Link

L2-043 龙龙送外卖

题意

龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。
每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……
看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。
思路

题目大意：每增加一个新的节点，就要求根节点到所有新增节点(包括之前的新增节点)的最短路径。

方法：最短路径 = 经过的路径*2(因为要计算重复路径)-当前所有新增节点的最长路径。文章来源地址https://www.toymoban.com/news/detail-424702.html
- 先DFS出每个点的深度
- 再从给的点往上遍历，因为父节点唯一，所以叶节点去往根节点的路径唯一
  - 如果到了根节点，那就是深度
  - 如果在中途遇到了已经到过的点（比如之前遍历的时候就到过的点），那么就直接返回0，因为可以再送途中顺便送了
- 最后结果减去当前最深深度，也就是不回去了

代码

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

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m;

vector <int> g[N];
int depth[N], vis[N], fa[N];

void dfs(int u, int x)
{
    depth[u] = x;
    for(auto v : g[u]){
        dfs(v, x + 1);
    }
}

int dfs2(int u)
{
    if(vis[u]) return 0;
    vis[u] = 1;
    return 1 + dfs2(fa[u]);
}

signed main()
{
    IOS;
    cin >> n >> m;
    int root;
    for(int i = 1; i <= n; ++ i){
        int u;
        cin >> u;
        if(u != -1) g[u].push_back(i);
        else root = i;
        fa[i] = u;
    }
    int ans = 0;

    dfs(root, 0);
    vis[root] = 1;

    int mx = 0;
    while(m --){
        int x;
        cin >> x;
        ans += dfs2(x) * 2;
        mx = max(mx, depth[x]);
        cout << ans - mx << '\n';
    }
    return 0;
}