CF-1073-F. Prufer Vertex（对于零散的图，计数可以从联通块角度考虑）（使用概率来计数） · znzryb
## 题目大意
### 题目总结：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. **添加边 (1,2) 和 (1,3)：** 叶子节点为 2 和 3。最小叶子 2 被删除，剩余 $\{1, 3\}$。故 $P(T)=1$。
1. **添加边 (2,1) 和 (2,3)：** 叶子节点为 1 和 3。最小叶子 1 被删除，剩余 $\{2, 3\}$。故 $P(T)=2$。
1. **添加边 (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$ 的子树下，是必要条件，是必须满足的。
你就抓住这个，进行分类讨论即可，因为太过细节，这里就不展开了。
然后，你会发现**答案不对**。
```cpp
_______________[ 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代码
AC
[https://codeforces.com/contest/2191/submission/360174534](https://codeforces.com/contest/2191/submission/360174534)
::: 源代码
```cpp
/**
* 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$ 的子树下，是必要条件，是必须满足的。