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

_Ch1F4N_ · 2026-10-17 23:27:12 · 题解

先考虑写个形式比较好的正确的暴力。

首先建圆方树。下面认为一次访问是从堆中取出这个点。

首先考察一个环上的点，在环上最靠近 1 的点 u 被访问后会对环上的点造成可能的两次访问，容易计算出 v 两次访问时用于更新的 dis 是 dis_u 加多少（注意与 u 相邻的两个点都会在第一次访问时被更新 dis），不妨记为 x_v,y_v。

考虑从上往下分析，这是因为想要更新 u 的 dis 必须先更新 u 在圆方树上最近的圆点祖先的 dis，所以从下往上分析就不太好。

不妨设 u 在圆方树上最近的圆点祖先被访问时的 dis 为 t_1>t_2>\dots>t_k，那么若 x_u \leq y_u 则 u 被访问时的 dis 一定为 t_1-x_u,t_2-x_u,\dots,t_k-x_u。否则为 t_1-x_u,t_1-y_u,(t_2-x_u),t_2-y_u,\dots,(t_k-x_u),t_k-y_u，其中打括号的 dis 不一定会在某次访问中出现，其会出现当且仅当其严格小于前一项。

不妨对结构稍加变化方便刻画，容易发现我们本质只在乎访问时的 dis 序列的相邻两项之差（有了这个就可以知道所有括号的存在性），所以当 u 在圆方树上最近的圆点祖先被访问时的 dis 序列的所有相邻两项构成 S 时，u 自己被访问时的 dis 序列的所有相邻两项差构成的集合 T 满足如下：若 x_u \leq y_u 则 T=S，否则先考察 S 中所有元素 z，若 z \leq (x_u-y_u) 则将 z 插入 T，否则将 x-(x_u-y_u),x_u-y_u 插入 T。再往 T 中插入一个 x_u-y_u。

考虑拆贡献，不妨将贡献拆到 S,T 中的每一个元素上，设 dp_{u,i} 表示传输到 u 子树（让所有 u 向圆方树上最近的圆点祖先连边建立一棵新树）的一个 dis 序列相邻两项的差 i 会在 u 整个子树的考虑过程中一共被拆出多少贡献。那么 \sum_{i=1}^n [x_i > y_i] dp_{i,x_i-y_i}+n 就是答案。

不妨 d_u=\max(0,x_u-y_u)，容易发现转移形如 dp_{u,i}=\sum_{v \in son_u} [i \leq d_v](dp_{v,i})+[i>d_v])(dp_{v,i-d_v}+dp_{v,d_v})，容易发现 dp_{v,i} 在 i > sz_v 时的取值是固定的，考虑使用启发式合并优化：对于重儿子平移 dp 数组的下标再处理 [1,d_v] 上的贡献（由于 \sum d_{son_u} 是 O(n) 的所有没关系，这里注意我们可能把定义域外的贡献平移进来了，要减去），对于轻儿子先考察让所有 dp_{v,i} 减去 dp_{v,sz_v+1}，那么枚举 dp_{v,i} 的非 0 项也就是 [1,sz_v] 上的加到 dp_{u,i} 中，而 dp_{v,sz_v+1} 的贡献形如一个全局和和前缀加，并且前缀不超过 d_v，因此把所有前缀加存起来最后处理即可（如果存的是全局变量注意不要让递归过程将其破坏了）。

使用哈希表，时间复杂度 O(n \log n)，注意访问一个哈希表中的空节点时精细处理避免新建多余的节点。并且事实上不用真的建圆方树，在 tarjan 过程中处理一下就行，具体可以见代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5+114;
vector<int> E[maxn];
int fa[maxn];
int n,m;
array<int,2> t[maxn];
int dfn[maxn],low[maxn],dfncnt;
int stk[maxn],tp;
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    stk[++tp]=u;
    for(int v:E[u]){
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                vector<int> seq;
                while(stk[tp]!=v){
                    seq.push_back(stk[tp]);
                    tp--;
                }
                seq.push_back(v);
                tp--;
                if(seq.back()<seq[0]) reverse(seq.begin(),seq.end());
                for(int x:seq) fa[x]=u;
                for(int i=0;i<(int)seq.size();i++) t[seq[i]]={(i==(int)seq.size()-1?1:i+1),(int)seq.size()-i};
            }
        }else low[u]=min(low[u],dfn[v]);
    }
}
vector<int> tr[maxn];
int sz[maxn];
int son[maxn];
void dfs(int u){
    sz[u]=1;
    for(int v:tr[u]){
        dfs(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
unordered_map<int,int> dp[maxn];
int tagv[maxn],tagi[maxn];
int tag[maxn];
int ans;
inline int get(int u,int i){
    auto it=dp[u].find(i);
    return it==dp[u].end()?0:it->second;
}
void DP(int u){
    int mx=0;
    for(int v:tr[u]) DP(v);
    if(son[u]!=0){
        int d=max(0*1ll,t[son[u]][0]-t[son[u]][1]);
        int c=(d>0?get(son[u],d-tagi[son[u]])+tagv[son[u]]:0);
        vector<int> f(d+1);
        for(int i=1;i<=d;i++) f[i]=get(son[u],i-tagi[son[u]])+tagv[son[u]];
        swap(dp[u],dp[son[u]]);
        swap(tagv[u],tagv[son[u]]);
        swap(tagi[u],tagi[son[u]]);
        tagi[u]+=d;
        for(int i=1;i<=d;i++){
            dp[u][i-tagi[u]]=-tagv[u];
        }
        for(int i=1;i<=d;i++) dp[u][i-tagi[u]]+=f[i]-c;
        tagv[u]+=(c+1);
        for(int v:tr[u]){
            if(v!=son[u]){
                int c=get(v,sz[v]+1-tagi[v])+tagv[v];
                tagv[v]-=c;
                int d=max(0*1ll,t[v][0]-t[v][1]);
                if(d==0){
                    tagv[u]+=c;
                    for(int i=1;i<=sz[v];i++){
                        dp[u][i-tagi[u]]+=get(v,i-tagi[v])+tagv[v];
                    }
                }else{
                    int C=c+get(v,d-tagi[v])+tagv[v];
                    tagv[u]+=c+C;
                    mx=max(mx,d);
                    tag[d]-=C;
                    for(int i=1;i<=sz[v];i++){
                        int val=get(v,i-tagi[v])+tagv[v];
                        if(i<=d) dp[u][i-tagi[u]]+=val;
                        dp[u][i-tagi[u]+d]+=val;
                    }
                }
            }
        }
    }else tagv[u]++;
    if(mx>0){
        for(int i=mx;i>1;i--) tag[i-1]+=tag[i];
        for(int i=1;i<=mx;i++) dp[u][i-tagi[u]]+=tag[i],tag[i]=0;
    }
    if(t[u][0]>t[u][1]) ans+=get(u,t[u][0]-t[u][1]-tagi[u])+tagv[u];
}
void work(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    tarjan(1);
    for(int i=2;i<=n;i++) tr[fa[i]].push_back(i);
    dfs(1);
    ans=n;
    DP(1);
    cout<<ans<<"\n";
    for(int i=0;i<=n;i++){
        fa[i]=0;
        sz[i]=son[i]=0;
        E[i].clear();
        tr[i].clear();
        stk[i]=dfn[i]=low[i]=0;
        t[i]={0,0};
        dp[i].clear();
        tagv[i]=tagi[i]=0;
    }
    tp=0;
    dfncnt=0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int c,t;
    cin>>c>>t;
    while(t--) work();
    return 0;
}