之前没做过无标号有根树有关的题目，考场上写个错的DP过了 (30pts)...
首先根据题目的条件，我们在脑海中大概能想象出这棵树的样子。假设初始状态只有两个相连的点，其中一个是根，另一个是叶子。定义一次生长为：在一个叶子下面接上三个新点。发现符合条件的树只能由初始状态生长若干次得到。题目就转化为了 (n) 次生长后形成的无标号有根树计数。
考虑树形DP：设 (f_i) 表示经过 (i) 次生长后本质不同的树的数量。(f_i) 可以分三类统计（因为一个节点下面只能挂三个叶子，所以自然的想到枚举每个子树生长多少次。另，下面的 (i-1) 中减一的原因是这个点本身要生长一次）：
- 下面挂的三个叶子生长次数两两不同。这时直接保证枚举的生长次数 (j<k<l) 即可保证没有重复，即 (f_i+=sumlimits_{j<k<l}[j+k+l=i-1]f_j imes f_k imes f_l)。
- 下面挂的三个叶子其中两个生长次数是相同的。思考方向就是要保证不重不漏：(f_i+=sumlimits_{2j+k=i-1}[j eq k]f_k imes (f_j+inom {f_j} 2))。
- 下面挂的三个叶子的生长次数都相同（首先要保证 (i-1equiv 0 pmod 3)）：(f_i+=inom {f_j} 3 +2inom {f_j} 2+f_j)（(j=frac{i-1}3)）。
时间复杂度 (O(n^3))，可以通过此题（但是计蒜客上直接能草过去emmm）。
但按照道理说 (O(n^3)) 是不行的qwq，所以我们有一个小小的trick。
设 (g_{i,j}=sumlimits_{k<l<j}[k+l==i-1]f_k imes f_l)，那么上面第一类就可以写成这样：(f_i+=sumlimits_{j=0}^{i-1} f_j imes g_{i-j,j})。然后 (g,f) 互相转化就可以做到 (O(n^2)) 的复杂度了。
代码（因为懒得优化直接写了个 (O(n^3)) 的）：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1009,M=998244353;
int n;
LL f[N],inv2,inv6;
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=1ll*res*a%M;
b>>=1,a=1ll*a*a%M;
}
return res;
}
void init()
{
scanf("%d",&n);
inv2=ksm(2,M-2),inv6=ksm(6,M-2);
}
void work()
{
f[0]=f[1]=1;
for (int i=2;i<=n;i++)
{
for (int j=0;j<=i-1;j++)
for (int k=j+1;k<=i-1-j;k++)
{
int l=i-1-j-k;
if(l<=k) continue;
f[i]=(f[i]+f[j]*f[k]%M*f[l]%M)%M;
}
for (int j=0;j<=i-1;j++)
{
int k=i-1-2*j;
if(k<0||k==j) continue;
f[i]=(f[i]+f[k]*((f[j]*(f[j]-1)%M*inv2%M+f[j])%M)%M)%M;
}
if((i-1)%3==0)
{
LL j=f[(i-1)/3];
f[i]=(f[i]+j*(j+1)%M*(j+2)%M*inv6%M)%M;
}
}
printf("%lld
",f[n]);
}
int main()
{
init();
work();
return 0;
}