-
度数均小于 \(3\) 则是条链,必然可以选出一个结点作为根,形成内向树或外向树 。(1)
-
否则若 \(deg_u = 3\)。
-
\(u\) 的边方向唯一,则形成以 \(u\) 为根的内向树或外向树。(1)
-
若存在 \(deg_v = 3, u \neq v\),它们的边不完全相同,
则树必然由一棵外向树和一棵内向树用一条链串起来,且两个树的根度数为 \(2\)。(2)
-
否则,是一个外向树或内向树。(1)
-
-
然后可以通过递推求出 \(f_i\): 直径为 \(i\) 的外向树每个点度数不超过 \(2\) 的方案数。
-
对于 (1),最后根结点度数可以为 \(3\),特别计算一下然后乘以 \(2\) (内向树对应外向树) 减去 \(1\) (单链重复计算)。
-
对于 (2),枚举外向树的直径,然后通过前缀和可以快速计算。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int fpow_(int a, int b, int res = 1) {
for (; b; b >>= 1, a = 1ll*a*a%mod)
if (b&1)
res = 1ll*res*a%mod;
return res;
}
int n, i2 = fpow_(2, mod - 2), i6 = fpow_(6, mod - 2), ans, f[N], g[N], h[N];
int cal_(int x, int k) {
if (k == 2)
return 1ll*x*(x + 1)%mod*i2%mod;
return 1ll*x*(1ll*x*(x + 3)%mod + 2)%mod*i6%mod;
}
int main() {
scanf("%lld", &n), n++;
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = (cal_(g[i - 1], 2) - cal_(g[i - 1] - f[i - 1], 2))%mod;
g[i] = (g[i - 1] + f[i])%mod, h[i] = (1ll*h[i - 1] + f[i] - f[i - 1])%mod;
}
ans = 2ll*(cal_(g[n - 1], 3) - cal_(g[n - 1] - f[n - 1], 3))%mod - 1;
for (int i = 2; i <= n - 2; i++)
ans = (ans + 1ll*(f[i] - f[i - 1])*h[n - i])%mod;
printf("%d\n", (ans + mod)%mod);
}