题解：CF2190D Prufer Vertex

MaxBlazeResFire · 2026-01-19 13:28:59 · 题解

刻画条件。显然，v 想要留下的充要条件是把边 (n,v) 拎起来后，n-1 不位于 n 的一侧（当然，v=n-1 是平凡的）。也就是 v 是 n 在 n-1 方向上的邻点。

要求 v 的答案，先把 n 和 v 连起来。如果 n-1 的情形已经确定了，那剩下的随便连。否则设现在这个连通块总体的点数为 N，v 一侧的点数为 M，则答案就是其余部分任意连的方案数乘以 \displaystyle\frac{M}{N}。因为我们把这个连通块缩起来之后，每个点都是等方案数地被挂到。

问题变为枚举每个 v 后直接维护这个东西。复杂度 O(n)。

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

#define int long long
#define MAXN 200005
#define mod 998244353

int n,m,siz[MAXN],rt[MAXN],id[MAXN],c = 0,Fa[MAXN],ans[MAXN],fpn[MAXN];
int inv[MAXN];
vector<int> E[MAXN];

void dfs( int x , int fa , int Id ){
    siz[x] = 1;
    if( fa == 0 ) rt[x] = x;
    else rt[x] = rt[fa];
    id[x] = Id,Fa[x] = fa;
    for( int v : E[x] ){
        if( v == fa ) continue;
        dfs( v , x , Id ),siz[x] += siz[v];
    }
}

inline void solve(){
    scanf("%lld%lld",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ){
        int u,v; scanf("%lld%lld",&u,&v);
        E[u].emplace_back( v ),E[v].emplace_back( u );
    }
    for( int i = n ; i >= 1 ; i -- ){ if( !rt[i] ) c ++,dfs( i , 0 , c ); }
    for( int i = 1 ; i <= n ; i ++ ) if( id[i] != id[n] ) siz[i] = siz[rt[i]];
    int S = 1;
    for( int i = 1 ; i <= n ; i ++ ) if( rt[i] == i ) S = S * siz[i] % mod;
    fpn[0] = 1;
    for( int i = 1 ; i <= n ; i ++ ) fpn[i] = fpn[i - 1] * n % mod;
    if( id[n] == id[n - 1] ){
        int now = n - 1;
        while( Fa[now] != n ) now = Fa[now];
        if( c == 1 ) ans[now] = 1;
        else ans[now] = fpn[c - 2] * S % mod;
    }
    else{
        for( int ele : E[n] )
            ans[ele] = fpn[c - 2] * S % mod * inv[siz[n]] % mod * siz[ele] % mod;
        for( int i = 1 ; i <= n ; i ++ ){
            if( id[i] != id[n] ){
                int nS = S * inv[siz[i]] % mod * inv[siz[n]] % mod * ( siz[i] + siz[n] ) % mod;
                if( id[i] == id[n - 1] ){
                    if( c == 2 ) ans[i] = 1;
                    else ans[i] = nS * fpn[c - 3] % mod;
                }
                else{
                    ans[i] = nS * fpn[c - 3] % mod * inv[siz[i] + siz[n]] % mod * siz[i] % mod;
                }
            }
        }
    }
    for( int i = 1 ; i < n ; i ++ ) printf("%lld ",ans[i]);
    puts("");
    for( int i = 1 ; i <= n ; i ++ ) E[i].clear(),ans[i] = id[i] = rt[i] = siz[i] = Fa[i] = fpn[i] = 0;
    c = 0;
}

signed main(){
    inv[1] = 1;
    for( int i = 2 ; i < MAXN ; i ++ ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}