P6890

Miraik · 2022-11-18 08:28:49 · 题解

对于每棵内向基环树，我们首先不管环，把其他节点解决掉。

考虑一种贪心的想法：连叶子节点，然后将当前距离 \le k 的点删掉，再继续连叶子节点，直至环外所有点都被删去。正确性比较显然，因为这样你自下而上拓展的速度最快。DFS 或 拓扑排序 都可以解决。

考虑环怎么办。刚才处理完了环外的点，因此现在 1 号节点到环上每点的距离是已知的。不妨先利用每个点到 1 号节点的距离在环上差分一下，可以求出那些与 1 号节点距离大于 k 的点，看作关键点。然后暴力扫描，枚举其中一个关键点作为起点，在环上不停向后覆盖，每覆盖一次都直接将指针向后移 k 步，这样我们单次扫描的复杂度就是 O(\frac{len}{k}) 的了（len 为环长）。

注意到我们只需要枚举前 k 个关键点（至多前 k 个为一段，那么以它们作为起点的情况已经包含了所有形态），因此对每个环我们这样做的复杂度就是 O(\frac{len}{k} \times k)=O(len)。

总时间复杂度 O(n)。有一点点细节，比如说 1 号点在环外计算时的特殊处理。

void tarjan(int u){ // tarjan 找环
    dfn[u]=low[u]=(++idx);
    stc[++top]=u; ins[u]=1;
    int v=to[u];
    if(!dfn[v]){
        tarjan(v);
        low[u]=min(low[u],low[v]);
    }
    else if(ins[v]) low[u]=min(low[u],dfn[v]);
    if(low[u]==dfn[u]){
        if(stc[top]==u){
            ins[stc[top]]=0; top--;
            return;
        }
        t++;
        while(stc[top]^u)
            g[t].emplace_back(stc[top]),ins[stc[top]]=0,top--;
        g[t].emplace_back(stc[top]),ins[stc[top]]=0,top--;
    }
}
inline int nd(int x){ // x 节点是否被覆盖
    if(x>m) x-=m;
    return c[x]==0;
}
void solve(int x){
    m=g[x].size();
    for(int i=1;i<=m;i++) a[i]=g[x][m-i],c[i]=0; // 注意是 m-i，tarjan 找出来的环是反向的！！！调了好久
    for(int i=1;i<=m;i++){ // 在环上差分
        int tar=i+k-f[a[i]];
        if(tar<=m) c[i]++,c[tar+1]--;
        else c[i]++,c[1]++,c[tar-m+1]--;
    }
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    cnt=0;
    for(int i=1;i<=m;i++) if(nd(i)) b[++cnt]=i;
    cir=cnt;
    for(int i=1;i<=min(k,cnt);i++){
        int tt=0;
        for(int j=b[i];j<b[i]+m;j++)
            if(nd(j)) tt++,j+=k-1;
        cir=min(cir,tt);
    }
    ans+=cir;
}
main(){
    read(n); read(k);
    for(int i=1;i<=n;i++){
        int u,v; read(u); read(v);
        if(u==v){ to[u]=u; continue; }
        to[u]=v; deg[v]++;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++) f[i]=k+1;
    for(int i=1;i<=n;i++)
        if(deg[i]==0 || i==1){ // 注意 i=1 的特殊处理
            if(i>1) f[i]=1,ans++;
            else f[i]=0;
            q.push(i);
        }
    while(!q.empty()){
        int u=q.front(); q.pop();
        if(f[u]>k) f[u]=1,ans++; // 距离 > k 且不在环上，给你连条边
        int v=to[u];
        if(v==1) continue;
        f[v]=min(f[v],f[u]+1);
        deg[v]--;
        if(!deg[v]) q.push(v);
    }
    for(int x=1;x<=t;x++) solve(x);
    print(ans);
}