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

· · 题解

提供一种不用圆方树，也不需要用 map 或deque 的 \mathcal{O}(n + m) 做法。

思路

首先有一个基本性质：每次成功更新 d_v 丢进集合的二元组，一定会在 v 被下一次更新前取出来。因为如果要把 d_v 更新得更小，得先取出一个 d_u + 1 < d_v 的点 u，但算法优先取距离最大的点，显然会先把 (v, d_v) 取出来。

所以每次距离变小都会贡献一次计数。每个点第一次被访问到的贡献合起来是 n，接下来只需要算每个点因为走更短路导致距离变小所带来的额外更新次数。

考虑一个环，设最先走到的点（环顶）为 u，环长为 L，环上的点依次为 u = v_0, v_1, \dots, v_{L - 1}, u，且满足 v_1 < v_{L - 1}。

当 u 拓展完后，v_1 和 v_{L - 1} 的距离都是 d_u + 1。因为优先取编号小的，算法会先顺着 v_1 这边一路走到底。

因此只有后半段满足 \frac{L}{2} < i < L - 1 的点，会先算出一个错的距离，再被正确的最短路更新。设长路比短路多出来的长度为 w，则环上这些点的 w_{v_i} = 2i - L，其余点（包括割边）的 w = 0。

写代码的时候直接在 DFS 树上找返祖边把环抠出来，把环上除环顶外的所有点直接连到环顶下面当儿子即可。

接下来考虑 DP。设 f_{u, x} 表示 u 子树内的距离都已经稳定后，把 d_u 减小 x，u 子树内会多出多少次更新（包含 u 自己）。显然 f_{u, 0} = 0。

枚举 u 的儿子 v，考虑 d_u 减小 x（x > 0）时对 v 的影响：

再加上 u 自己的一次更新，转移就是：

f_{u, x} = 1 + \sum_{v \in \text{son}(u)} \begin{cases} f_{v, x} & x \le w_v \\ f_{v, x - w_v} + f_{v, w_v} & x > w_v \end{cases}

另外，第一次进环的时候，每个 w_v > 0 的点本身就会经历一次从长路变成短路的过程，距离减小了 w_v，对答案有 f_{v, w_v} 的贡献。所以总答案就是：

n + \sum_{v = 2}^n f_{v, w_v}

维护

直接维护 f_{u, x} 不太好做，考虑维护它在第二维上的差分数组 a_{u, i} = f_{u, i} - f_{u, i - 1}。这样求 f_{v, w_v} 就是求 a_v 的前 w_v 项和。

看一眼上面的转移式在差分数组上是怎么变的：前 w_v 项的差分不变；从第 w_v + 1 项开始，差分依次变成了 a_{v, 1}, a_{v, 2}, \dots。 也就是说，儿子 v 往父亲转移时，相当于把 a_v 的前 w_v 项复制一份，直接拼到原序列 a_v 的最前面，然后再加到父亲的差分数组上。最后给父亲的第一项 a_{u, 1} 加 1 即可。

这个东西可以直接用类似长链剖分的方式在数组上维护。设 sz_u 为 u 的差分数组长度，有：

sz_u = \max\left(1, \max_{v \in \text{son}(u)} (sz_v + w_v)\right)

我们选 sz_v + w_v 最大的儿子作为重儿子 h。开一个全局大数组 dp，记 u 的差分数组在 dp 里的起始下标为 cl_u，直接令重儿子的起始位置往后错开 w_h 位：

cl_h = cl_u + w_h

等重儿子做完后，它的原序列已经正好在父亲需要的后半段位置上了，只需要把重儿子的前 w_h 项复制到前面的 cl_u \sim cl_u + w_h - 1 即可。轻儿子就另开空间递归算完，再暴力把每一项加过来。

求答案时，我们在把儿子的前 w_v 项往父亲前面复制/累加的时候，顺便把这前 w_v 项的值加到全局 ans 里，就刚好把 \sum f_{v, w_v} 算完了。

最后算一下空间和复杂度：只有每条重链的链首需要分配新空间，沿着重链把 sz_u = sz_h + w_h 展开消掉，总分配长度是：

\sum_{\text{链首 } u} sz_u = \text{叶子数} + \sum_{u} w_{h_u}

每个环顶最多选一个重儿子，所以每个环最多在右边贡献一次 w，而环上点的 w 小于环长，所以 \sum w_{h_u} < n，总空间小于 2n，dp 数组开两倍就够了。所有轻儿子的长度和也是这个量级，所以时间复杂度和空间复杂度都是严格的 \mathcal{O}(n + m)。

声明：本文由 Gemini 4-Argon 润色，感谢其提供的类长链剖分 \mathcal{O}(n + m) 思路优化以及复杂度证明。保证人类贡献严格大于 AI SI 的贡献。

代码


#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,c,T,dep[N],fa[N],pa[N],w[N],sz[N],hson[N];
long long ans;
vector<int> v1[N],vec[N];
int cl[N],dp[N*2],nodecnt;
void dfs(int p){
    for(auto k:v1[p]){
        if(k==fa[p]) continue;
        if(dep[k]==0){
            fa[k]=pa[k]=p;dep[k]=dep[p]+1;
            dfs(k);
        }
        else if(dep[k]<dep[p]){
            vector<int> v;
            for(int u=p;u!=k;u=fa[u]) v.push_back(u);
            v.push_back(k);reverse(v.begin(),v.end());
            int len=v.size();
            if(v[1]>v.back()) reverse(v.begin()+1,v.end());
            for(int i=1;i<len;i++){
                pa[v[i]]=k;
                if(2*i>len&&i<len-1) w[v[i]]=2*i-len;
            }
        }
    }
}
void dfs1(int p){
    sz[p]=1;
    for(auto k:vec[p]){
        dfs1(k);
        if(!hson[p]||sz[k]+w[k]>sz[p]){
            sz[p]=sz[k]+w[k];
            hson[p]=k;
        }
    }
}
void calc(int p){
    if(!cl[p]){
        cl[p]=nodecnt+1;
        nodecnt+=sz[p];
    }
    if(!hson[p]){
        dp[cl[p]]=1;
        return;
    }
    cl[hson[p]]=cl[p]+w[hson[p]];
    calc(hson[p]);
    for(int i=0;i<min(w[hson[p]],sz[hson[p]]);i++){
        dp[cl[p]+i]=dp[cl[hson[p]]+i];
        ans+=dp[cl[p]+i];
    }
    for(auto k:vec[p]){
        if(k==hson[p]) continue;
        calc(k);
        for(int i=0;i<sz[k];i++){
            dp[cl[p]+i+w[k]]+=dp[cl[k]+i];
            if(i<w[k]) dp[cl[p]+i]+=dp[cl[k]+i],ans+=dp[cl[k]+i];
        }
    }
    dp[cl[p]]++;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>c>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            v1[i].clear(),vec[i].clear();
            dep[i]=fa[i]=pa[i]=w[i]=sz[i]=hson[i]=cl[i]=0;
        }
        nodecnt=0;
        for(int i=1;i<=2*n+1;i++) dp[i]=0;
        for(int i=1;i<=m;i++){
            int u,v;cin>>u>>v;
            v1[u].push_back(v);v1[v].push_back(u);
        }
        dep[1]=1;dfs(1);
        for(int i=2;i<=n;i++) vec[pa[i]].push_back(i);
        dfs1(1);
        ans=n;calc(1);
        cout<<ans<<'\n';
    }
    return 0;
}