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

· · 题解

本题解部分参考了这篇题解。

感觉题解区的题解都比较难懂，所以写一篇详细一点的。

初步感受

考虑对于一个没有被走过的环，算法会怎样更新它。

假设这个环的环顶是 u，环长是 L，u 两侧的点分别为 v_1,v_{L-1}，且 v_1<v_{L-1}。那么算法首先会更新 d_u，然后更新 d_{v_1} 和 d_{v_{L-1}}，然后顺着 v_1 这一侧一路更新到 v_{L-2}，并且在过程中更新每个环上点的“子树”。随后从 v_{L-2} 一路再更新回来，直到某个 v_i 满足 i\leq L-i 结束这一更新过程。

对于这个环上一个被更新两次的点，定义其“长路”为第一次从 u 更新到它所走的路径，“短路”则为第二次更新时的路径。考虑如果下次再更新这个环时，长路不一定可以一路更新完这个环，因为某个点这一次更新走长路的距离可能已经小于上一次更新走短路的距离，这时长路的更新到此为止。

动态规划

对每个点 i 规定一个值 w_i。如果 i 是上一段中被更新两次的环点，定义 w_i 为长路长度减去短路长度；否则令 w_i=0。

接下来我们考虑 DP。对于一个非环顶点，为了方便我们让它去当环顶的儿子。定义 f_{u,i} 表示当 u 子树内的点已经被全部更新完成时，如果令 d_u 减少 i，则会造成子树内多少次更新。对于每个点 u，它们最初被访问到时会造成 1 的贡献，而第一次被访问之后从所在环的短路更新回来时会带领整颗子树造成 f_{u,w_u} 的贡献。因此答案即为

\boxed{\text{ans} = n+\sum_{u>1}f_{u,w_u}}

考虑 f 如何进行转移。如果 d_u 减少了 i，那么对于 u 的某个儿子 v 而言，如果 i>w_v，意味着这次走长路要比上次走短路更短，因此算法会先走长路让 d_v 减少 i-w_v，然后再走短路让 d_v 减少 w_v，因此对父亲 u 的贡献是 f_{v,i-w_v}+f_{v,w_v}；否则这次只能通过走短路更新 v 的子树，因此贡献是 f_{v,i}。再考虑到 u 自己会被更新一次，因此有转移方程

f_{v,i-w_v}+f_{v,w_v}&,i>w_v \\f_{v,i}&,i\leq w_v \end{cases}}

特别地有 f_{u,0}=0。直接暴力转移可以获得 55 分。

优化转移

接下来我们考虑优化这个 DP。这看起来十分困难，迫使我们寻找其性质。

如果你有超人的洞察能力，可以观察到如下性质。设 a_{u,i}=f_{u,i}-f_{u,i-1}，即令 a 为 f 第二维的差分数组，我们考虑 a_v 对 a_u 的转移。对于 i\leq w_v，相当于把对应的 a_{v,i} 加到 a_{u,i} 上；而对于 i>w_v，相当于加上 a_{v,i-w_v}。

类似 dsu on tree，我们定义 \text{siz}_u 表示 a_u 中非零部分的长度，则根据转移式子有 \text{siz}_u=\max(1,w_v+\text{siz}_v)。定义一个点的重儿子 h_u 为 u 的所有儿子中 \text{siz} 最大的那一个。那么我们可以把 a_{h_u} 的前 w_{h_u} 项复制到 a_{h_u} 开头，然后把 a_{h_u} 作为只转移了 h_u 的 a_u，这样直接完成了 a_{h_u} 对 a_u 的转移。

具体地，我们定义一个大数组 g，每个点 u 的差分 DP 数组 a_u 都可以表示成 g 中的一个区间 [s_u,s_u+\text{siz}_u-1]。每次要求 a_u 时，先令 s_{h_u}\leftarrow s_u+w_{h_u}，其他儿子 v 分别开辟 g 中新的空间，然后递归处理所有儿子；接下来再把重儿子数组的前 w_{h_u} 项加在 a_u 的前 w_{h_u} 项上（如果没有这么多项就只转移 \text{siz}_{h_u} 项），轻儿子暴力更新转移；最后还要把 g_{s_u} 加上 1。每次转移时直接把儿子的前 w_v 项和加入全局答案，就可以求出最终结果。

考虑上面这个算法的时间和空间复杂度。对于空间而言，每次开辟 g 中新空间的点一定是所有链顶，考虑一条链链顶的 \text{siz} 应当是整条链除去链顶的 w 之和再加上 1，这样对于原图中的一个环，环顶最多只会选择一个重儿子，因此每个环贡献一个 w，因此所有链上的 w 之和应当不超过 n，因此 g 的总大小不会超过 2n。对于时间而言，每个重儿子会贡献一个 w，其总和不超过 n；而每个轻儿子 u 贡献为 \min(\text{siz}_u,w_u)+\text{siz}_u，由前述得轻儿子的 \text{siz} 总和不超过 n，因此轻儿子的时间贡献总量级也是 O(n)；故总时间复杂度为 O(n+m)。

:::success[代码]

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
int c,T;
int n,m;
struct EDGE{
    int u,v,nxt;
}edge[1500005],tmp[1500005];
int head[500005],tot;
void add(int u,int v){
    edge[++tot]={u,v,head[u]};
    head[u]=tot;
}
int in[500005],vis[500005];
int st[500005],top;
int w[500005];
vector<int>a;
vector<pair<int,int> >b;
void dfs1(int x,int fa){
    in[x]=1;
    vis[x]=1;st[++top]=x;
    int qwq=0;
    for(int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)continue;
        if(vis[v]){
            if(in[v])qwq=v;
            continue;
        }
        dfs1(v,x);
    }
    if(qwq){
        int len=1,now=top;
        a.clear();
        while(st[now]!=qwq){
            len++;
            a.push_back(st[now]);
            b.push_back({qwq,st[now]});
            now--;
        }
        if(a[0]>a[len-2])reverse(a.begin(),a.end());
        for(int i=1;i<a.size()-1;i++){
            w[a[i]]=max(0ll,2*(i+1)-len);
        }
    }
    in[x]=0;top--;
}
int F[500005];
int Find(int x){
    if(F[x]==x)return x;
    return F[x]=Find(F[x]);
}
int siz[500005],hson[500005];
void dfs2(int x,int fa){
    siz[x]=1;
    for(int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)continue;
        dfs2(v,x);
        siz[x]=max(siz[x],siz[v]+w[v]);
        if(siz[v]>siz[hson[x]])hson[x]=v;
    }
}
int f[1000005],s[500005];
int now,ans;
void dfs3(int x,int fa){
    if(hson[x]){
        s[hson[x]]=s[x]+w[hson[x]];
        dfs3(hson[x],x);
        for(int i=1;i<=min(siz[hson[x]],w[hson[x]]);i++){
            f[s[x]+i-1]+=f[s[hson[x]]+i-1];
            ans+=f[s[hson[x]]+i-1];
        }
    }
    for(int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa||v==hson[x])continue;
        s[v]=now;now+=siz[v];
        dfs3(v,x);
        for(int j=1;j<=min(w[v],siz[v]);j++){
            f[s[x]+j-1]+=f[s[v]+j-1];
            ans+=f[s[v]+j-1];
        }
        for(int j=1;j<=siz[v];j++)f[s[x]+w[v]+j-1]+=f[s[v]+j-1];
    }
    f[s[x]]++;
}
void init(){
    now=ans=0;
    for(int i=1;i<=n;i++)s[i]=siz[i]=hson[i]=F[i]=w[i]=st[i]=vis[i]=in[i]=head[i]=0;
    for(int i=1;i<=2*n;i++)f[i]=0;
    for(int i=1;i<=tot;i++)edge[i]=tmp[i]={0,0,0};
    top=tot=0;
    a.clear();b.clear();
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>c>>T;
    while(T--){
        init();
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int u,v;cin>>u>>v;
            add(u,v),add(v,u);
        }
        dfs1(1,0);
        int awa=tot; 
        for(int i=1;i<=tot;i++)tmp[i]=edge[i],edge[i]={0,0,0};
        for(int i=1;i<=n;i++)head[i]=0,F[i]=i;
        tot=0;
        for(int i=0;i<b.size();i++){
            int u=b[i].first,v=b[i].second;
            add(u,v);add(v,u);
            F[Find(u)]=Find(v); 
        }
        for(int i=1;i<=awa;i++){
            int u=tmp[i].u,v=tmp[i].v;
            if(Find(u)!=Find(v)){
                F[Find(u)]=Find(v);
                add(u,v);add(v,u);
            }
        }
        dfs2(1,0);
        s[1]=1;now=siz[1]+1;
        dfs3(1,0);
        cout<<ans+n<<'\n';
    }
    return 0;
}

:::