一个很套路的做法。
思路
题目要求走完整个树的时间，这并不好算，容易想到 min-max 容斥。
依据 min-max 容斥，我们可以轻松把它转化成第一次走到所有子集的时间。
考虑在这道题中，有什么特殊的。
第一，任何包含根节点的子集答案都是零。
第二，由于我们只关心第一次走到的点的时间，因此假如一个点的祖先被选中，那么这个点是否选中是无关紧要的。
这些无关紧要的点地位相同，所以我们可以一起考虑。
假设有 \(n\) 个点是无关紧要的。
它们对答案的贡献是什么呢？
是：
\[(-1)^k\sum_{i=0}^n (-1)^i\binom{n}{i} \]这是非常令人熟悉的二项式定理。
因此：
\[(-1)^k\sum_{i=0}^n (-1)^i\binom{n}{i} =(-1)^k[n=0] \]我们发现，只有当 \(n=0\) 的时候才对答案有贡献。
在 \(n=0\) 的时候，每一条链只有最底部的点可能被选。
现在计算这样的时间即可。
首先，对于底部被选的链而言。
我们设 \(f_i\) 表示到达深度为 \(i\) 的点还要走的期望步数，根节点的深度为 \(0\)。
那么有：
\[\begin{align} f_m&=0\nonumber\\ f_{m-1}&=\frac{(f_m+f_{m-2})}{2}+1\nonumber\\ &=\frac{f_{m-2}}{2}+1\nonumber\\ f_{m-2}&=\frac{f_{m-3}+f_{m-1}}{2}+1\nonumber\\ &=\frac{f_{m-3}+\frac{f_{m-2}}{2}+1}{2}+1\nonumber\\ &=\frac{2f_{m-3}}{3}+2\nonumber\\ f_{m-i}&=\frac{if_{m-i-1}}{i+1}+i\nonumber\\ \end{align} \]对于底部没有被选的链而言。
有：
\[\begin{align} f_n&=f_{m-1}+1\nonumber\\ f_{m-1}&=\frac{(f_n+f_{m-2})}{2}+1\nonumber\\ &=f_{m-2}+3\nonumber\\ f_{m-i}&=f_{m-i}+2\times i +1\nonumber\\ \end{align} \]所有期望都可以推到根上。
因此，假设有 \(i\) 条链被选，则有 \((n-i)\) 条链没有被选：
\[f_{0}=\frac{i(\frac{(m-1)f_0}{m}+m-1)+(n-i)(f_0+2\times m-1)}{n}+1 \]可以继续化简。
\[\begin{align} f_{0}&=\frac{i(\frac{(m-1)f_0}{m}+m-1)+(n-i)(f_0+2\times m-1)}{n}+1\nonumber\\ \frac{i}{n}f_{0}&=\frac{i(\frac{(m-1)f_0}{m}+m-1)+(n-i)(2\times m-1)}{n}+1\nonumber\\ (\frac{i}{n}-\frac{i(m-1)}{nm})f_{0}&=\frac{i(m-1)+(n-i)(2\times m-1)}{n}+1\nonumber\\ (i-\frac{i(m-1)}{m})f_{0}&=i(m-1)+(n-i)(2\times m-1)+n\nonumber\\ \frac{i}{m}f_{0}&=i(m-1)+(n-i)(2\times m-1)+n\nonumber\\ \end{align} \]算出 \(f_0\) 后，不要忘记乘负一和组合数的系数。
时间复杂度：\(O(n\log mod)\)。
瓶颈在求逆元，可以线性预处理，但没有必要。
Code
/*
! 前途似海，来日方长。
! Created: 2024/10/13 21:48:58
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();
using i64 = long long;
using pii = pair<int, int>;
bool ST;
const int N = 1e6 + 10;
const int mod = 998244353;
int n, m;
namespace Math {
int Fc[1000010], Iv[1000010];
template<typename T> inline void add(T&x, int y) { if ((x += y) >= mod) x -= mod; }
template<typename T> inline void del(T&x, int y) { if ((x -= y) < 0) x += mod; }
template<typename T> inline void add(T&x, int y, int z) { x = (x + (long long) y * z) % mod; }
template<typename T> inline void mo(T&x) { x = (x % mod + mod) % mod; }
inline long long power(long long x, long long y) {
long long res = 1;
while (y) { if (y & 1) res = res * x % mod; x = x * x % mod, y /= 2; }
return res;
}
inline void init(int n) {
Fc[0] = 1;
for (int i = 1; i <= n; i++) Fc[i] = (long long) Fc[i - 1] * i % mod; Iv[n] = power(Fc[n], mod - 2);
for (int i = n; i >= 1; i--) Iv[i - 1] = (long long) Iv[i] * i % mod;
}
inline long long C(int x, int y) { return (x < 0 || y < 0 || x < y ? 0 : (long long) Fc[x] * Iv[y] % mod * Iv[x - y] % mod); }
} using namespace Math;
signed main() {
JYFILE19();
cin >> n >> m, init(n);
int ns = 0;
fro(i, 1, n) {
int x = C(n, i);
int up = (i * (m - 1) + (n - i) * (2 * m - 1)) % mod;
int dw = (i * power(m, mod - 2)) % mod;
int sm = ((up + n) * power(dw, mod - 2)) % mod;
ns = (ns + (i & 1 ? 1 : -1) * x * sm) % mod;
}
cout << (ns % mod + mod) % mod << "\n";
return 0;
}
bool ED;
inline void JYFILE19() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
srand(random_device{}());
ios::sync_with_stdio(0), cin.tie(0);
double MIB = fabs((&ED - &ST) / 1048576.), LIM = 32;
cerr << "MEMORY: " << MIB << endl, assert(MIB <= LIM);
}