2022 团体程序设计天梯赛 L2-3

题意

给定一棵无向树，m次标记点，标记点的同时询问从根出发访问所有点的最短路径和。走到最后一个点不用返回。

思路

逆向思维，考虑加入一个点的时候，可以走的最优方案。
对于一个新加入的点，如果可以从计划访问的点，走到这个新的点，那么是较优的选择。
考虑从新加入的点逐级回溯，如果可以到达某个计划访问的点，那么从该点出发到这个新加入的点是最优方案。
由于走到最后一个点不用返回，所以方案调整为：走到最深的点不再返回。所以dfs记录深度，同时维护当前最大深度即可。

solution

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
const int N = 1e5 + 7;
bool vis[N];  // 记录访问标记
int fa[N];    // 记录父节点
int go(int x) {
    int ans = 0;
    while (!vis[x]) {  // 向上回溯，直到找到遍历过的点为止
        vis[x] = 1;
        ans += 2;
        x = fa[x];  // 路上加入访问标记
    }
    return ans;
}
vector<int> G[N];
int d[N];
void dfs(int fa, int dep = 0) {  // 遍历树，标记深度
    d[fa] = dep;
    for (int x : G[fa]) {
        dfs(x, dep + 1);
    }
}
signed main() {
    int n, m, rt;
    cin >> n >> m;

    rep(i, 1, n) {
        cin >> fa[i];
        if (fa[i] == -1)  // 标记根节点
            rt = i;
        else
            G[fa[i]].push_back(i);  // 建树
    }
    vis[rt] = 1;  // 初始时根已访问
    dfs(rt);
    int x, maxd = 0, ans = 0;
    while (m--) {
        cin >> x;
        ans += go(x);
        maxd = max(maxd, d[x]);  // 更新最大深度
        cout << ans - maxd;      // 最大深度的那个点最后走
        if (m) cout << '\n';
    }

    return 0;
}