C++11(clang++ 3.9) 解法, 执行用时: 326ms, 内存消耗: 10332K, 提交时间: 2018-11-24 09:10:47

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T&x,const T &y)
{
	if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
	char c;
	while(gc<'-');
	if(c=='-')
	{
		int x=gc-'0';
		while(gc>='0')x=x*10+c-'0';
		return -x;
	}
	int x=c-'0';
	while(gc>='0')x=x*10+c-'0';
	return x;
}
#undef gc

const int K=15,D=998244353;
int n,k;
struct Tree
{ 
static const int N=500+5;
vector<int>lk[N];
s64 dp[N][K][K][K],f[K][K];
void dfs(int x,int fr)
{
	dp[x][0][0][1]=1;
	for(auto y:lk[x])
	if(y!=fr)
	{
		dfs(y,x);
		per(ax,k,0)
		per(bx,k,0)
		per(cx,k,0)
		{
			s64 fx=dp[x][ax][bx][cx];
			if(!fx)continue;
			dp[x][ax][bx][cx]=0;
			rep(ay,0,k)
			rep(by,0,k-bx)
			rep(cy,0,k)
			{
				s64 fy=dp[y][ay][by][cy];
				if(!fy)continue;
				fy=fy*fx%D;
				if(cy==0||cy==1)(dp[x][ax+ay][bx+by][cx]+=fy)%=D;
				if(!cx||!cy)continue;
				if(bx+by+cx+cy<=k)
					(dp[x][ax+ay+1][bx+by+cx+cy][0]+=fy)%=D;
				if(cx==1&&cx+cy<=k)(dp[x][ax+ay][bx+by][cx+cy]+=fy)%=D;
			}
		}
	}
}
void init()
{
	rep(i,1,n-1)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		lk[x].push_back(y);
		lk[y].push_back(x);
	}
	dfs(1,0);
	rep(a,0,k)
	rep(b,0,k)
	{
		rep(c,0,1)f[a][b]+=dp[1][a][b][c];
		(f[a][b]<<=a)%=D;
		rep(i,1,a)(f[a][b]*=i)%=D;
	}
}
}T[3];
unordered_map<int,int>dp[3];
const int w[3]={1,K,K*K};
s64 check(int s)
{
	s64 ans=0;
	static int a[3];
	rep(i,0,2){a[i]=s%K;s/=K;}
	rep(b0,a[0]*2,k)
	rep(b1,a[1]*2,k-b0)
		(ans+=T[0].f[a[0]][b0]*T[1].f[a[1]][b1]%D*T[2].f[a[2]][k-b0-b1])%=D;
	return ans;
}
int dfs(int s,int i,int k)
{
	s+=w[i];k-=2;
	if(dp[i].count(s))return dp[i][s];
	s64 ans=check(s);
	if(k>=2)
	rep(j,0,2)
	if(j!=i)ans+=dfs(s,j,k);
	//assert(ans>=0);
	return dp[i][s]=ans%D;
}

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
	cin>>n>>k;
	if(k==1)
	{
		puts("0");
		//cout<<3*n;
		exit(0);
	}
/*	if(k==2)
	{
		cout<<3*2*(n-1);
		exit(0);
	}*/
	rep(i,0,2)T[i].init();
//	memset(dp,-1,sizeof(dp));
	s64 ans=0;	
	rep(i,0,2)ans+=dfs(0,i,k);
	assert(ans>=0);
	cout<<ans%D<<endl;
}