作者在草稿纸上其实把三种情况都画出来了，但是没有想到情况只有这三种。瞄了一眼题解之后，推 DP 式子就较为简单了。

还是对这种找性质题记一笔。以后遇到这种题不要畏难，多做一做就出来了。

考虑第三个条件如何转化。其实需要发现，任意两点 之间的简单路径上，只能有一对相邻边的方向不同，否则 肯定找不到共同的能到达它或它能到达的点。容易发现，外向树或内向树都是一种不同相邻边不超过 的方案，然而事实上还有一种，就是一棵内向树和一棵外向树在根处拼接，这个时候，对于内向树中的点 和外向树中的点 ， 之间的边方向全都相同。

首先考虑外向树的方案数，这种树除了根以外都只能有 个儿子，那么先设 表示最大深度为 ，根最多两个儿子的方案数，设 表示 的前缀和。

考虑 的转移：

1. 只有一个儿子，此时 。
2. 有两个儿子，此时必须有一个儿子的深度为 。先考虑所有儿子深度 的方案数，是 ，（为什么不是 呢，因为如果两个子树的儿子形态不同，在这个式子里会被算两次，所以需要去重，就变成了上面这个组合数），再减去所有儿子深度 的方案数，就得到了至少有一个儿子深度为 的方案数。

综上所述，。

那么，深度为 的内向树的方案就有 种，外向树同理。但因为一条单链会被内向树 和外向树都算一遍，所以这一部分的答案是上式乘 再减 。

再考虑内向树拼外向树怎么做。这两部分中间可能有一条链相连接，为了避免在这条链上重复计数，我们钦定外向树部分的根有恰好两个儿子 。设 表示 ，即深度为 ，且根恰好有两个儿子的方案数。那么答案就是 。减 是因为如果内向树部分是一条单链，那接起来之后还是一棵外向树，这一部分在前面算过了。

于是本题就做完了，时间复杂度 。难点在于归纳答案的形态。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5,P = 998244353;
const int inv2 = (P + 1) / 2,inv6 = (P + 1) / 6;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n;
int f[N],g[N];
int sf[N];
inline int C2(int x) { return 1ll * x * (x - 1) % P * inv2 % P;}
inline int C3(int x) { return 1ll * x * (x - 1) % P * (x - 2) % P * inv6 % P;}
int main()
{
	cin >> n;
	// if(n == 1) { puts("5");return 0;}
	f[0] = sf[0] = 1;
	for(int i = 1;i <= n;i++)
	{
		f[i] = f[i - 1];
		Plus(f[i],(C2(sf[i - 1] + 1) - (i >= 2 ? C2(sf[i - 2] + 1) : 0) + P) % P);
		sf[i] = sf[i - 1];Plus(sf[i],f[i]);
	}
	int ans = C3(sf[n - 1] + 2);
	if(n >= 2) Plus(ans,P - C3(sf[n - 2] + 2)); // 外向树方案
	Plus(ans,f[n]);
	ans = (2ll * ans - 1 + P) % P; // 最终方案
	g[1] = 1;

	for(int i = 2;i <= n;i++) 
		g[i] = (C2(sf[i - 1] + 1) - C2(sf[i - 2] + 1) + P) % P;
	for(int i = 1;i < n - 1;i++)
		Plus(ans,1ll * g[i] * (f[n - 1 - i] - 1 + P) % P);
	cout << ans << endl;
	return 0;
}