记录编号	613501	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[省选联考 2026] 找寻者	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	5.627 s
提交时间	2026-03-14 18:02:20	内存使用	73.02 MiB

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=5005;
const int mod=998244353;
typedef long long ll;
int c,t,n,dep[N],sz[N],L[N];
ll f[N][N],g[N][N],tmp[N],ans,inv[N],val[N];
vector<int>G[N];
void clear(){
	ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=sz[i];j++){
			f[i][j]=g[i][j]=0;
		}
		sz[i]=dep[i]=L[i]=0;
		G[i].clear();
	}
	return;
}
void add(int x,int y){
	G[x].push_back(y);
}
ll ksm(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1; 
	}
	return ans;
}
void dfs(int x,int fa){
	int son=0;
	dep[x]=1;
	for(auto y:G[x]){
		if(y==fa)continue;
		dfs(y,x);son++; 
		dep[x]=max(dep[x],dep[y]+1);
	}
	if(!son){
		sz[x]=1;
		f[x][1]=1;
	}else{
		g[x][0]=1,L[x]=0;
		for(auto y:G[x]){
			if(y==fa)continue;
			for(int i=0;i<=L[x];i++){
				for(int j=1;j<=dep[y];j++){
					(tmp[i+j]+=g[x][i]*f[y][j]%mod)%=mod;
				}
			}
			sz[x]+=sz[y];
			L[x]+=dep[y];
			for(int i=0;i<=L[x];i++){
				g[x][i]=tmp[i];
				tmp[i]=0;
			}
		}
		for(auto y:G[x]){
			if(y==fa)continue;
			int mx=-1;
			for(int i=dep[y];i>=1;i--){
				if(!f[y][i])continue;
				mx=i;break;
			}
			for(int i=0;i<=L[x];i++){
				tmp[i]=g[x][i];
			}
			if(mx!=-1){
				ll invf=ksm(f[y][mx],mod-2);
				for(int i=L[x];i>=mx;i--){
					if(!tmp[i])continue;
					ll inv=invf*tmp[i]%mod;
					val[i-mx]=inv;
					for(int j=0;j<=mx;j++){
						tmp[i-j]-=f[y][mx-j]*inv%mod;
						tmp[i-j]%=mod;
					}
				}
			}
			ll p=0,e=0;
			for(int i=1;i<=mx;i++){
				for(int j=0;j<=L[x]-mx;j++){
					(p+=val[j]*inv[i+j]%mod)%=mod;
				}
				p=(p*f[y][i]%mod*i)%mod;
				(f[x][i+1]+=p)%=mod;
				(e+=p)%=mod,p=0;
			}
			(ans+=(1-e)*sz[y]%mod)%=mod;
			for(int i=0;i<=L[x];i++)tmp[i]=val[i]=0;
		}
		sz[x]++;
	}
	return;
}
void work(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++){
		scanf("%d %d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs(1,0);
	ans=(ans%mod+mod)%mod;
	printf("%lld\n",ans);
	return;
}
int main(){
	freopen("recollector.in","r",stdin);
	freopen("recollector.out","w",stdout);
	scanf("%d %d",&c,&t);
	inv[0]=1;
	for(int i=1;i<=5000;i++)inv[i]=ksm(i,mod-2);
	while(t--){
		work();
		clear();
	}
	return 0;
}