一道问号题，AT 赛场上没人通过。其实是联考题
这道题十分有意思，做法很简单但是要想到是极其困难的。考场上我也拿着推了很久猜测这个式子的组合意义，擦到了正解的一些边。然而正解的思想还是太反直觉了。
首先题目中的式子实际上是让我们对树上的边建一颗笛卡尔树，然后计算笛卡尔树所有子树大小 +1 的倒数乘积之和。
如果没有这个 +1 一切多么美好啊！相当于给边集随一个排列，然后用这个排列建笛卡尔树，众所周知由于树形拓扑序就是 \(\prod_u \frac{1}{sz_u}\)，所以我们只需要求出满足树形拓扑序的排列的出现概率就行了。推出来发现答案永远是 1。
同样的我们考虑用类似的方法对本题搞事情，我们对每一个边和点都建出点，有人会说：你这样点数还是不是 \(n\) 啊，所以我们再给每一个边点下面接 \(P-1\) 个叶子，那么在模意义下计算出来的 \(\frac{1}{n}\) 就是一模一样的了！
我们考虑同样对我们建出来的这些点随权值。树上笛卡尔树的建法是找到每个连通块中权值最小的那个点，而这里修改一下建法，如果权值最小的那个点不是边点的话，定义整个过程就失败了，否则就删掉对应的边递归下去，那么每个连通块不失败的概率就是题目中要求 \(\frac{1}{n}\)。我们发现对于一种赋权方案，过程最终不会失败当且仅当每一个边点都比相邻的点小，于是我们只要对这个东西计数就是答案了。
我们对每一个边点向父亲的连边直接容斥，发现就成了若干个森林的拓扑序方案，也是 \(\prod_u \frac{1}{sz_u}\)，树形背包就做完了！！！
#include <cstdio>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=5003,P=998244353;
typedef long long ll;
int n;
int hd[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){
nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;
}
int f[N][N],sz[N],tmp[N],inv[N];
void dfs(int u,int fa){
f[u][sz[u]=1]=1;
for(int i=hd[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa) continue;
dfs(v,u);
long long sum=0;
for(int j=1;j<=sz[v];++j) sum+=f[v][j];
for(int j=1;j<=sz[u];++j)
for(int k=1;k<=sz[v];++k)
tmp[j+k]=(tmp[j+k]+(ll)f[u][j]*f[v][k])%P;
sz[u]+=sz[v];
for(int j=1;j<=sz[u];++j){
f[u][j]=(sum%P*f[u][j]-tmp[j])%P;
if(f[u][j]<0) f[u][j]+=P;
tmp[j]=0;
}
}
for(int i=1;i<=sz[u];++i){
f[u][i]=(ll)f[u][i]*inv[i]%P;
if(fa) f[u][i]=(ll)f[u][i]*inv[i]%P;
}
}
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v);add(v,u);
}
inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
dfs(1,0);
long long res=0;
for(int i=1;i<=n;++i) res+=f[1][i];
printf("%d\n",int(res%P));
return 0;
}