题解：P8950 [YsOI2022] 道路修建

· · 题解

好题，补一下题解。

注意到对于 k=1 的情况不弱于最小树形图的板子。

回顾一下朱刘算法的过程：我们维护了一个内向树森林，每次取出一个没有出度的根节点 u，找到它的最小出边 v，则有两种情况：

但是缩点之后这个环内多了一条边。考虑环内的点 u，设它延伸出去的边长度为 d，则如果别的边从 u 连出去，则需要断开 d 这条边。所以我们需要枚举 u 的所有边，并且将其长度减去 d，这样就正确了。

用带懒标记的可并堆去快速找到每个点的最小出边，复杂度为 O(n\log n)。

考虑拆贡献，计算每条边被包含的次数。

设我们现在考虑到 u\to v 这条边。记 S_u 表示 u 节点包含的原图中的点的集合，则如果没有点在 S_u 内，则 S_u 中的点就会从这条边中走出去，贡献系数为 \dfrac {\binom{n-|S_u|}{k} }{\binom{n}{k}}。

判断无解也是简单的：如果最终发现有一个根节点 u 满足 |S_u|+k\le n，则我们可以把这 k 个节点全部扔到 S_u 的外面，这样就寄了。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace io{

template<typename T>
inline void gi(T &x)
{
    x=0;char ch=getchar();
    while(ch<'0'||'9'<ch) ch=getchar();
    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
template<typename T>
void print(T x)
{
    if(x<=9) return putchar(x+'0'),void();
    print(x/10),putchar(x%10+'0');
}

}using io::gi;using io::print;

const int N=5e5+9;
const int mod=998244353;

int fac[N],inv[N],ifac[N];
void ycl(int lim=2e5)
{
    fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=1;
    for(int i=2;i<=lim;i++)
    {
        fac[i]=1ll*fac[i-1]*i%mod;
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
    }
}
int C(int x,int y){return x>=y&&y>=0?1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod:0;}
int invC(int x,int y){return x>=y&&y>=0?1ll*ifac[x]*fac[y]%mod*fac[x-y]%mod:0;}

pii val[N];
int siz[N],son[N][2],tag[N],dep[N],tcnt=0;
int new_node(pii x)
{
    int u=++tcnt;
    siz[u]=1;tag[u]=son[u][0]=son[u][1]=0;
    val[u]=x;
    return u;
}
void Add(int u,int x){if(u) val[u].first+=x,tag[u]+=x;}
void pushdown(int u){if(tag[u]) Add(son[u][0],tag[u]),Add(son[u][1],tag[u]),tag[u]=0;}
void pushup(int u){siz[u]=siz[son[u][0]]+siz[son[u][1]]+1,dep[u]=dep[son[u][1]]+1;}
int Merge(int u,int v)
{
    if(!u||!v) return u+v;
    pushdown(u),pushdown(v);
    if(val[u]>val[v]) swap(u,v);
    son[u][1]=Merge(son[u][1],v);
    if(dep[son[u][0]]<dep[son[u][1]]) swap(son[u][0],son[u][1]);
    return pushup(u),u;
}
void pop(int &rt){pushdown(rt);rt=Merge(son[rt][0],son[rt][1]);}

int n,m,K;

int rt[N];

int nxt[N],len[N],tp[N];
int siz1[N];
int gettp(int x){return tp[x]==x?x:tp[x]=gettp(tp[x]);}

int bcj[N];
int getfa(int x){return bcj[x]==x?x:bcj[x]=getfa(bcj[x]);}

signed main()
{
    ycl();
    gi(n),gi(m),gi(K);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        gi(u),gi(v),gi(w);
        if(u!=v)
        rt[u]=Merge(rt[u],new_node(make_pair(w,v)));
    }
    for(int i=1;i<=n;i++) bcj[i]=tp[i]=i;
    for(int i=1;i<=n;i++) siz1[i]=1;
    int ans=0;
    for(int u=1;u<=n;u++)
    {
        while(siz[rt[u]])
        {
            int v=val[rt[u]].second;
            if(gettp(u)==gettp(v)) {pop(rt[u]);continue;}
            (ans+=1ll*C(n-siz1[gettp(u)],K)*(val[rt[u]].first%mod+mod)%mod)%=mod;
            if(getfa(u)==getfa(v))
            {
                int uu=gettp(v),d=val[rt[u]].first;
                pop(rt[u]);
                Add(rt[u],-d);
                while(uu!=u)
                {
                    Add(rt[uu],-len[uu]);
                    rt[u]=Merge(rt[u],rt[uu]);
                    uu=gettp(nxt[uu]);
                }
                uu=gettp(v);
                while(uu!=u)
                {
                    siz1[u]+=siz1[uu];
                    bcj[uu]=tp[uu]=u;
                    uu=gettp(nxt[uu]);
                }
            }
            else
            {
                nxt[u]=gettp(v),len[u]=val[rt[u]].first;
                bcj[u]=v;
                break;
            }
        }
        if(!siz[rt[u]])
        {
            if(siz1[u]+K<=n) return puts("-1"),0;
            continue;
        }
    }
    print(1ll*ans*invC(n,K)%mod);
}