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

· · 题解

很好写的做法，甚至不用圆方树。

令 dp_{u,i} 表示 u 子树内的 d 都确定为以 d_u 为确定初值得到真实的 d 后，d_u\to d_u-i 的总更新次数，注意 dp_{u,0}=0。

每个含 u 的环独立做，对于一个环形如后半段做一个转移，可以求出一个数组 a_u 使得对于一个环，dp_{u,x} 从一个环上的点 v 转移的贡献是，当 x\leq a_v 则贡献 dp_{v,x} 否则贡献 dp_{v,x-a_v}+dp_{v,a_v}，割边则直接转移 dp_{v,x}。

维护 dp_u 的差分 diff，那么这个变换就形如把 diff_{1},diff_2,\cdots,diff_{a_u} 接到原有 diff 序列的前面，然后再逐项相加。逐项相加用 map 启发式合并即可 O(n\log^2n)，细节维护所有项的和 su 以及差分的平移标记 tag，暴力往前面添加项，操作次数是 \min(siz_u,a_u)，而这里有一个类似于启发式合并的性质，所以 map 的总操作次数仍然是 O(n\log n)。

时间复杂度 O(n\log^2n)，空间复杂度 O(n\log n)。

写的时候发现只需要在 \text{DFS} 树上做，直接把每个环的点贡献到环的顶点上。我猜精细实现是可以把 map 的 \log 去掉的，但是懒了。

#include<bits/stdc++.h>
#define bll __int128
#define ull unsigned long long
#define ll long long
#define uint unsigned
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1073741824
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
bool ST;
void fre(){
    // freopen(".in","r",stdin),freopen(".out","w",stdout);
}
inline int lowbit(int x){ return x&(-x); }
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=2000005;
int testid,n,zsy;
struct ds{
    map<int,ll>mp;
    int tag;
    ll su;
    void init(){
        mp.clear(),tag=su=0;
    }
    void add(int pos,ll val){
        mp[pos-tag]+=val,su+=val;
    }
    void trans(int x){
        if(x<=0||mp.empty())return;
        auto R=mp.upper_bound(x-tag);
        for(auto it=mp.begin();it!=R;++it)mp.emplace((it->fi)-x,it->se),su+=it->se;
        tag+=x;
    }
}f[maxn];
void merge(ds&a,ds&b){
    if(SZ(a.mp)<SZ(b.mp))a.mp.swap(b.mp),swap(a.tag,b.tag),swap(a.su,b.su);
    a.su+=b.su;
    for(auto it=b.mp.begin();it!=b.mp.end();++it)a.mp[(it->fi)+b.tag-a.tag]+=it->se;
}
int dfn[maxn],rev[maxn],tim,fa[maxn];
vector<int>g[maxn];
void dfs0(int u){
    rev[dfn[u]=++tim]=u;
    for(int&v:g[u])if(!dfn[v])fa[v]=u,dfs0(v);
}
bool inr[maxn];
int a[maxn],up[maxn];
void solve(){
    cin>>n>>zsy,tim=0;
    F(i,1,n)g[i].clear(),fa[i]=inr[i]=dfn[i]=a[i]=up[i]=0,f[i].init();
    F(_,1,zsy){ int u,v;cin>>u>>v,g[u].push_back(v),g[v].push_back(u); }
    dfs0(1);
    F(u,1,n)for(int&v:g[u])if(dfn[v]<dfn[u]&&v!=fa[u]){
        vector<int>vec;
        for(int x=u;x!=v;x=fa[x])inr[x]=1,vec.push_back(x);
        reverse(all(vec));
        bool fl=vec[0]<vec.back();
        int len=SZ(vec);
        F(i,0,len-1){
            int x=fl?vec[i]:vec[len-1-i];
            up[x]=v,a[x]=(((i+1)<<1)>len+1&&i+1<len)?((i+1)<<1)-(len+1):0;
        }
    }
    F(i,2,n)if(!inr[i])a[i]=0,up[i]=fa[i];
    dF(_,n,1){
        const int u=rev[_];
        f[u].add(1,1);
        if(u==1)break;
        if(a[u])f[u].trans(a[u]);
        merge(f[up[u]],f[u]);
        map<int,ll>().swap(f[u].mp);
    }
    cout<<f[1].su<<'\n';
}
bool ED;
signed main(){
    fre(),ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int zsy=1;cin>>testid>>zsy;
    F(____,1,zsy)solve();
    cerr<<"time used: "<<(double)clock()/CLOCKS_PER_SEC<<endl;
    cerr<<"memory used: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB"<<endl;
}
// g++ C.cpp -o a -std=c++14 -O2