CF-1073-F. Prufer Vertex（对于零散的图，计数可以从联通块角度考虑）（使用概率来计数）

题目大意

题目总结：F. Prufer Vertex

1. Prufer 顶点 $P(T)$ 的定义

对于一棵拥有 $n \ge 2$ 个节点的树 $T$ ，按照以下标准过程生成 Prufer 序列：

重复寻找当前树中编号最小的叶子节点并将其删除。
直到树中只剩下最后 2 个节点。
已知节点 $n$ 必然是最后剩下的两个节点之一，设另一个剩下的节点为 $v$ ，则定义该树的 Prufer 顶点 $P(T) = v$ 。

2. 问题描述

给定一个含有 $n$ 个顶点和 $m$ 条边的森林。假设该森林有 $k$ 个连通块，其大小分别为 $s_1, s_2, \dots, s_k$ 。

已知将该森林添加 $k-1$ 条边使其成为一棵树的方案总数为：

n^{k-2} \prod_{i=1}^{k} s_i

任务： 对于每一个 $v$ ( $1 \le v < n$ )，计算在所有可能的加边成树方案中，满足 $P(T) = v$ 的方案数量。

3. 输出要求

输出 $n-1$ 个整数，第 $i$ 个整数表示满足 $P(T) = i$ 的方案数，结果对 $998244353$ 取模。

样例解释（以样例 1 为例）：

输入 $n=3, m=0$ ，森林由三个孤立点 $\{1, 2, 3\}$ 组成。补全为树的方案共有 $3^{3-2} \cdot (1 \cdot 1 \cdot 1) = 3$ 种：

添加边 (1,2) 和 (1,3)： 叶子节点为 2 和 3。最小叶子 2 被删除，剩余 $\{1, 3\}$ 。故 $P(T)=1$ 。
添加边 (2,1) 和 (2,3)： 叶子节点为 1 和 3。最小叶子 1 被删除，剩余 $\{2, 3\}$ 。故 $P(T)=2$ 。
添加边 (3,1) 和 (3,2)： 叶子节点为 1 和 2。最小叶子 1 被删除，此时 2 变为叶子，删除 2，剩余 $\{3\}$ 与另一节点（在此情况下 Prufer 过程最后剩下的非 $n$ 节点为 2）。

最终输出：1 2（代表 $P(T)=1$ 有 1 种， $P(T)=2$ 有 2 种）。

思路讲解

我们阐述一下题意，叶子在无根树树中应该就是指的是度为 1 的点（虽然给的是森林，不过我们最后都会连成树），样例 1 的答案生成过程如图所示：

我们发现，只要一个点，是只和最大点相连的点（最大点和该点连接且仅和该点连接），那么这个点一定可以被保下来。因为这个点，是最后成为这个叶子节点的。原因：反证法，如果比较早把这个点删除了，那么最大点就变为孤零零一个人了，这显然是不可能的。

那么更进一步的推论就是，答案一定是和最大点直接相连的点。不过，虽然我们知道了答案是和最大点直接相连的点，但是我们不太清楚，到底是哪个点。

我们进行一个猜测，就是以这个点为根的子树，其内部的最大点，是所有的子树中最大的（即其他子树中的最大点，都比这颗子树小）。这样子，在删除这个内部最大点之前，我们会把其他子树全部删除，最后就只剩一颗子树了，结果就确定了。

当然，这个所谓的内部最大点，就是次大值 $n-1$ 啦，以 $n$ 为根， $n-1$ 所在的子树的根就是所能留下来的点。

不过现在的难点就来到了这个统计答案。

从 $n-1$ 的特殊情况看起，我们发现，如果 $n-1$ 已经连接在了 $n$ 的联通块上，且 $n-1$ 与 $n$ 之间未直接相连，此时答案为 0。如果直接相连，那么其实其他连通块要连接到 $n$ 的连通块上，这个要怎么算呢？我们不妨参考一下题目中的这个式子。

给定一个含有 $n$ 个顶点和 $m$ 条边的森林。假设该森林有 $k$ 个连通块，其大小分别为 $s_1, s_2, \dots, s_k$ 。已知将该森林添加 $k-1$ 条边使其成为一棵树的方案总数为：

n^{k-2} \prod_{i=1}^{k} s_i

实际上这个式子是凯莱公式的推论？

我们先来看一下凯莱公式吧，凯莱公式即：

其证明方法有：

呃😅，那我们还是用这个 prufer 序列吧，其实 prufer 序列就是把题目中描述的删点过程：每次我们记录一下这个我们删的点的父节点，得到的就是长度为 $n-2$ 的 prufer 序列。这个序列有 $n^{n-2}$ 种选择，由于每颗生成树对应的 prufer 序列显然是唯一的，prufer 序列也唯一对应一颗生成树，因此生成树的数量就是 $n^{n-2}$ （这个说的比较粗糙，只是引入一下 prufer 序列这个工具，帮助后面我们的这个理解）。

那么这个连通块的式子是怎么来的？

首先从 prufer 序列的角度来看，那么由于其中的每个点，都可以作为长度为 $k-2$ 的 prufer 序列中的点，所以就是 $n^{k-2}$ ，那么由于每个连通块还需选出来一个代表点连接，因此是：

n^{k-2} \prod_{i=1}^{k} s_i

可以想象， $n^{k-2}$ 代表了这个接收端， $\prod_{i=1}^{k} s_i$ 代表了这个发送端。不过还有一个特例，就是没有被 prufer 序列覆盖的根连通块的这个贡献也包含在了这个 $\prod_{i=1}^{k} s_i$ 当中。换句话说，一个长度为 $k-2$ 的 prufer 序列的贡献是 $\prod_{i=1}^{k} s_i$ **，原因在于你要确定所有非根连通块的发送端****（**这个是固定的，只有一个的，否则会成环），还要确定根连通块的接收端（在 prufer 中未体现）（严格来讲是最后一个被删除的块所连接的这个根连通块的接收点）。

哎，我们回来看题目：

我们之前所说的结论：

以 $n$ 为根， $n-1$ 所在的子树的根就是所能留下来的点

说明， $n-1$ 连接在 $i$ 的子树下，是必要条件，是必须满足的。

你就抓住这个，进行分类讨论即可，因为太过细节，这里就不展开了。

然后，你会发现答案不对。

_______________[ Sample Testcase #1 OUTPUT]_______________
1 2
0 0 0 1
10 0 1 5 5

这道题目的难点，特别是计数难点在于，如何去解决一些先 $k$ 连通块连上 $i$ 的子树，然后 $n-1$ 再连上 $k$ 连通块去的这个情况（或者更加复杂情况下的计数）。

具体而言，我们以样例 3 的这个第一个计数为例：

但是这个计数问题我们怎么解决？

我们用算概率的方式，得到这个答案，具体而言：

为什么我们可以使用算概率的方式呢？实际上， $n-1$ 连接到 $1$ 的子树的概率就是 $\frac{1}{2}$ ，无论他是通过 $3$ 连接，还是不通过 $3$ 连接，都是这个概率。这个概率就起到了相当于抽丝剥茧，剥开重重迷雾的作用。

AC代码

https://codeforces.com/contest/2191/submission/360174534

源代码

/**
 * Problem: F. Prufer Vertex
 * Contest: Codeforces Round 1073 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2191/problem/F
 * Created: 2026-01-22 13:22:57
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <string>
#include <cstring>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 2e5 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

/**   并查集（DSU）
 *    2023-08-04: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63239142 (base on jiangly)
 *    2025-11-08: https://frp-shy.com:32768/domjudge/team H题 增加dsu on next，标记区间l，r的功能
 *    为了适配这个dsu on next，对merge 函数合并方向进行了修改。
 *    2025-12-05：https://codeforces.com/contest/2171/submission/351963922
 *    增加了 countFa 功能
 *    2025-12-23：移除了宏定义，增加功能说明模块。
 *    功能说明：dsu on next，find(x)，就是在 x 之后第一个没有被标记的数字
 *    该 dsu 传入构造函数的这个大小，需要是 n 就是 n，如果你不希望 countFa 出错的话。
**/
struct DSU {
    vector<int> fa, siz;
    ll n;

    DSU() {
    }

    DSU(ll n): n(n) {
        init(n + 5);
    }

    void init(ll n) {
        fa.resize(n);
        for (int i = 0; i < SZ(fa); ++i) {
            fa[i] = i;
        }
        siz.assign(n, 1);
    }

    ll find(ll x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[y] += siz[x];
        fa[x] = y;
        return true;
    }

    ll size(ll x) {
        return siz[find(x)];
    }

    // dsu on next 技巧，直接标记 [l,r] 这段区间
    // 标记就是指让[l,r]这段区间里的所有数字这个都不指向自己
    // 可以理解为指向 r+1
    void taglr(ll l, ll r) {
        l = max(0ll, l);
        r = min(SZ(fa) - 2, r);
        l = find(l);
        while (l <= r) {
            merge(l, l + 1);
            l += 1;
            l = find(l);
        }
    }

    ll countFa() {
        ll res = 0;
        for (int i = 1; i <= n; ++i) {
            if (fa[i] == i) {
                ++res;
            }
        }
        return res;
    }
};

// 在 k<=0 的时候返回 1
ll binpow(ll a, ll k, const ll &p = mod) {
    ll res = 1;
    a %= p;
    while (k > 0) {
        if ((k & 1) == 1) res = a * res % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<vector<ll> > g(N + 2);
    DSU fa(N);
    DSU without_edge_to_n_fa(N);
    map<ll, map<ll, bool> > u_to_v_mp;
    for (int i = 1; i <= M; ++i) {
        ll u, v;
        cin >> u >> v;
        u_to_v_mp[u][v] = true;
        u_to_v_mp[v][u] = true;
        // g[u].push_back(v);
        // g[v].push_back(u);
        fa.merge(u, v);
        if (u != N && v != N) {
            without_edge_to_n_fa.merge(u, v);
        }
    }
    ll mx_node_connect_to_n = 0;
    for (auto it: u_to_v_mp[N]) {
        mx_node_connect_to_n = max(mx_node_connect_to_n, it.first);
    }
    bool n_to_n_1 = u_to_v_mp[N].contains(N - 1);
    ll s_prod = 1;
    vector<char> vis_connect(N + 2);
    for (int i = 1; i <= N; ++i) {
        ll pa = fa.find(i);
        if (vis_connect[pa]) {
            continue;
        }
        vis_connect[pa] = true;
        s_prod *= fa.size(i);
        s_prod %= mod;
    }
    ll k_cntFa = fa.countFa();
    auto cal_ans = [&](ll k_rem_connect, vector<ll> divide_ls, bool iscal_sum = false)-> ll {
        if (k_rem_connect <= 1) return 1;
        if (iscal_sum) {
            // 计算总单答案，直接使用该式子计算即可
            ll res = s_prod * binpow(N, k_rem_connect - 2);
            res %= mod;
            return res;
        }
        ll multiple = accumulate(all(divide_ls), 0ll);
        ll op_s_prod = s_prod;
        for (auto divide: divide_ls) {
            op_s_prod *= binpow(divide, mod - 2);
            op_s_prod %= mod;
        }
        op_s_prod *= multiple;
        op_s_prod %= mod;
        ll res = binpow(N, k_rem_connect - 2) * op_s_prod % mod;
        if (res < 0) res += mod;
        return res;
    };
    // 我们下面再开一个答案计算函数，有点屎山，但是也没办法
    auto cal_ans2 = [&](ll k_rem_connect, vector<ll> divide_ls,ll sz_i_subtree,
        ll sz_n_component)-> ll {

        if (k_rem_connect <= 1) return 1;
        ll multiple = accumulate(all(divide_ls), 0ll);
        ll op_s_prod = s_prod;
        for (auto divide: divide_ls) {
            op_s_prod *= binpow(divide, mod - 2);
            op_s_prod %= mod;
        }
        op_s_prod *= multiple;
        op_s_prod %= mod;
        ll res = binpow(N, k_rem_connect - 2) * op_s_prod % mod;
        res*=sz_i_subtree;res%=mod;
        res*=binpow(sz_n_component,mod-2);res%=mod;
        if (res < 0) res += mod;
        return res;
    };
    for (int i = 1; i <= N - 1; ++i) {
        if (i == N - 1) {
            if (n_to_n_1) {
                // 总答案这样子计算有问题
                // ll ans=binpow(N,k_cntFa-2)*s_prod;
                ll ans = cal_ans(k_cntFa, {}, true);
                cout << ans << " ";
                continue;
            }
            if (fa.same(N, N - 1)) {
                cout << 0 << " ";
                continue;
            }
            ll ans = cal_ans(k_cntFa - 1, {fa.size(i), fa.size(N)});
            cout << ans << " ";
        } else {
            if (n_to_n_1) {
                cout << 0 << " ";
                continue;
            }
            // 处于同一连通块下
            if (fa.same(N, i)) {
                if (u_to_v_mp[N].contains(i)) {
                    if (fa.same(N - 1, N)) {
                        // N-1 已经在 i 的子树上，已经稳了，剩下的点随便怎么连接
                        if (without_edge_to_n_fa.same(N - 1, i)) {
                            // 就是直接计算总答案
                            ll ans = cal_ans(k_cntFa, {}, true);
                            cout << ans << " ";
                        } else {
                            // N-1 在 N 连通块，但是不在 i 的子树上，直接宣判死刑
                            cout << 0 << " ";
                        }
                    } else {
                        // N 和 i 直接相连
                        // 需要把 N-1 所在联通块连上 i 的子树
                        // 总共答案就是把这个 i 和 N-1连上以后的总答案，乘以 i 的子树大小
                        ll ans = cal_ans2(k_cntFa,{1},without_edge_to_n_fa.size(i),fa.size(N));
                        ans %= mod;
                        cout << ans << " ";
                    }
                } else {
                    // i 和 N 处于同一连通块的时候而且未直接相连，答案为 0。
                    cout << 0 << " ";
                    continue;
                }
            } else {
                if (fa.same(N, N - 1)) {
                    cout << 0 << " ";
                    continue;
                }
                ll ans;
                // 这里这个分类讨论，最开始的程序漏了
                if (fa.same(N-1,i)) {
                    ans=cal_ans(k_cntFa-1,{fa.size(i),fa.size(N)});
                }else {
                    // 我们现在必须要把这个 N-1连接到这个 i 上面（即 i 的子树，连通块上面）
                    ans = cal_ans2(k_cntFa - 1, {fa.size(i),fa.size(N)},
                        fa.size(i),fa.size(i)+fa.size(N));
                }
                cout << ans << " ";
            }
        }
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*
1
3 0

_______________[ Sample Testcase #1 OUTPUT]_______________
1 2
0 0 0 1
10 0 1 5 5

AC
https://codeforces.com/contest/2191/submission/360174534

*/

心路历程（WA，TLE，MLE……）

$n-1$ 的答案是：
- 如果 $n$ 与 $n-1$ 直接相连，答案就是 $n^{k-2} \prod_{i=1}^{k} s_i$ 。如果不直接相连，还处于同一联通块，那么答案是 0。那么最后一种更普遍的情况，就是 $n$ 与 $n-1$ 处于两个连通块，这个时候就将 $n$ 与 $n-1$ 连接在一起，形成的新的森林，用上面那个公式计算即可。
更加普遍的情况下， $i$ 的答案是：
- $i$ 与 $n$ 处于相同连通块：
- $i$ 与 $n$ 处于不同连通块：
  我们之前所说的结论：

以 $n$ 为根， $n-1$ 所在的子树的根就是所能留下来的点
说明， $n-1$ 连接在 $i$ 的子树下，是必要条件，是必须满足的。