题解：P17724 [SCP-S 2026] 路短最 / path

· · 题解

场上大战这个题两个小时失败，写篇题解。

手玩样例感受一下，Artskjid 相对于一个 BFS 更像 DFS。当遍历的对象是没有环时，遍历的方式是唯一的，C 也唯一取值 n。

当出现环，会发生什么事呢？对于一个长度为 L 的环 1,2,3,\dots,L。从 1 出发，首先更新 d_{2}=d_{L}=1，让后从 2 开始搜索，对于 2\le i<L，先依次执行 d_i=i，最后再从 L 开始搜索，把错误的最短路矫正回来。

不难发现，当若干个环拼在一起的时候，可以将一个问题划分成若干子问题来结局。假如说某个环上，点 x 第一个被更新，则他会把这个环上的所有点的最短路都进行一个更新，有的更新一次，有的更新两次。

考虑建一个类似圆方树的东西（从 1 开始搜素，对于一个环上的点，把其余点都挂在第一个搜到的点的下面）我们考虑对每个点求出 f_x 表示假如 x 是其子树里第一个更新的，则会对 C 产生多少次贡献。环上的每个点 y 的 f_y 可能会对 f_x 更新一次或者两次，做一个类似 dp 的东西就好了。

这是我的赛时做法，显然假了。如果把这个做法写出来，就会发现一大堆五元环嵌套的情况下，C 会指数级增长，错误的原因在于：假如 x 的最短路更新后只是减小了 1，则他从一侧开始的更新并不会更新所有的点。

举个例子：对于五元环 x_1\to x_2\to x_3\to x_4\to x_5，我们已经有了 d_{x_1}=v,d_{x_2}=d_{x_5}=v+1,d_{x_3}=d_{x_4}=v+2。当 d_{x_1}\gets v-1 的时候，从 x_2 开始的更新只会依次更新 d_{x_2}\gets v,d_{x_3}\gets v+1，而不会更新 x_4 了。

思考一下，发现错误的算法可以在这个反例是继续修改。不妨设，当前 d_x=v，且子树内所有点的 d_i 的值都更新完成了，考虑此时更新 d_x\gets v-i，则在子树内产生的更新次数为 f_{x,i}。

当 i 趋于正无穷的时候，相当于整个子树都被更新，产生的对 C 的贡献就不会变了，因此我们只需要记录唯一一个 f_{x,i} 的最大值即可。

考虑对每个环上的 x,y，从 x 出发的第一次更新 y 的最短路和二次更新后 y 的最短路相比偏差了 w_y，根据 w_y 来分类讨论。

对于任意的 i，x 的最短路减小只会更新 y 一次，有：f_{x,i}\gets f_{x,i}+f_{y,i}。

若 x 距离从 d 更新为 d-i，y 距离 x 为 t，则 y 会先从 d_y+t 更新为 d_y+t+w_y-i 再被更新为 d_y+t-i。分类讨论：

不难发现两种情况可以统一起来，得到最终的转移式：

\begin{cases} f_{x,i}+f_{y,i} & i\ge w_y \\ f_{x,i}+f_{y,i - w_y} + f_{y,w_y} & 1\le i < w_y \end{cases}

最后记得 f_{x,1}\gets f_{x,1}+1，发现好像对时间复杂度依然没有什么改善。考虑继续优化。

不难发现这个转移等价于将 f_{y} 的前 w_y 项加到 f_{x} 上。然后把整个 f_{y,i} 依次增加到 f_{x,w_{y}+i} 上，最后 f_{x,w_{y}} 这个位置及以后的 dp 值都增加 f_{y,w_y}。

考虑维护 g_{x,i}=f_{x,i}-f_{x,i-1}。转移式可以写成：

\begin{cases} g_{x,i}+g_{y,i} & i\ge w_y \\ g_{x,i}+g_{y,i - w_y} & 1\le i < w_y \end{cases}

最后只需要求出来一个 g_{1} 的前缀和，得到 f_{1,n} 就是答案。

先前提到过，f_{x,i} 的第二维实际上有一个范围 h_x，当 i>h_x 后，f_{x,i} 等价于 f_{x,h_x}，所以只需要维护 1\sim h_x 的 dp 值即可。

从上面的转移，可以得出 h_x=\max(h_y+w_y)。做一个类似长链剖分的东西，每次从 \max(h_y+w_y) 作为重儿子计算 dp，直接继承 g_{y,1\sim h_x} 到 g_{x,w_y+1\sim w_y+h_x}。然后把其他差分值加上。

我们像长链剖分一样分析复杂度：

对于空间复杂度：即所有长链的长度之和，不难发现每个叶子都会贡献 1，每个环上至多一个 w_y 会贡献一个小于环长的量。所以空间只需要开到 2n 即可。

对于时间复杂度：跨过轻边的代价等价于所有长链的长度之和，上面已证明为 O(n)，重边之间的代价分析类似：每个环上至多一个 w_y 会贡献一个小于环长的量，所以总的贡献也是 O(n)。

综上，在 O(n+m) 的复杂度内解决了这个问题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, m, son[N], md[N];
int Fa[N], de[N], w[N];
int st[N], tot;
vector<int> F[N], G[N];
ll f[N << 1], ans;
void clear() {
    for (int i = 1; i <= n; i++) {
        F[i].clear(), G[i].clear();
        Fa[i] = de[i] = w[i] = st[i] = 0;
        son[i] = md[i] = 0;
    }
    for (int i = 0; i <= tot + 1; i++) f[i] = 0;
    ans = tot = 0;
    return;
}
void link(int x, int y) {
    F[x].push_back(y);
}
void dfs1(int x, int fa) {
    de[x] = de[fa] + 1, Fa[x] = fa;
    for (auto y : F[x]) {
        if (y == fa) continue;
        if (de[y] && de[y] < de[x]) {
            vector<int> son;
            for (int i = x; i != y; i = Fa[i]) son.push_back(i);
            int len = son.size() + 1;
            if (son[0] > son.back()) reverse(son.begin(), son.end());
            for (int i = 0; i < son.size(); i++) {
                Fa[son[i]] = y;
                if (i >= len / 2 && i != son.size() - 1) {
                    w[son[i]] = i - (len - 2 - i);
                }
            }  
        } else if (!de[y]) dfs1(y, x);
    }
    return;
}
void add(int x, int y) {
    G[x].push_back(y);
}
void dfs2(int x) { 
    for (auto y : G[x]) {
        dfs2(y);
        if (md[y] + w[y] > md[x]) {
            md[x] = md[y] + w[y];
            son[x] = y;
        }
    }
    md[x] = max(md[x], 1);
    return;
}
void dfs3(int x) {
    if (!son[x]) { f[st[x]] += 1; return; }
    int y = son[x]; st[y] = st[x] + w[y]; dfs3(y);
    for (int i = 0; i < min(w[y], md[y]); i++) f[st[x] + i] = f[st[y] + i];
    for (auto y : G[x]) if (y != son[x]) {
        st[y] = tot, tot += md[y]; dfs3(y);
        if (!w[y]) {
            for (int i = 0; i < md[y]; i++) f[st[x] + i] += f[st[y] + i];
        } else {
            for (int i = 0; i < md[y]; i++) f[st[x] + i + w[y]] += f[st[y] + i];
            for (int i = 0; i < min(md[y], w[y]); i++) f[st[x] + i] += f[st[y] + i];
        }
    }
    f[st[x]] += 1;
    return;
}
void work() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        link(u, v), link(v, u);
    }
    dfs1(1, 0); 
    for (int i = 2; i <= n; i++) add(Fa[i], i);
    dfs2(1); st[1] = 0, tot = md[1]; dfs3(1);
    for (int i = 0; i < md[1]; i++) ans += f[i];
    cout << ans << '\n';
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int c, T; cin >> c >> T;
    while (T--) work(), clear();
    return 0;
}

如有错误，请指出。