好神仙的题目。赛时胡了一个状态和转移都和官解不同的做法，得到了 $O(n10^m)$ 的优秀复杂度。卡了一场常卡进了 $75$ 分。这个做法和官解关系不大，并且很难进行最后的优化部分，所以在此不再赘述。

首先考虑 $k=1$ 的情况。考虑记录一些状态能够描述子树内的选择方案，$0$ 表示整个子树没有被覆盖过，$1$ 表示子树内部有点被覆盖过并且子树外的点还能被覆盖，$2$ 表示子树内部有点被覆盖过并且子树外的点不能被覆盖了。考虑转移，需要把转移描述为只和 $u,v$ 有关的形式才能较为简单的扩展到 $k\neq 1$ 的情况。发现对于 $1\rightarrow 2$ 的转移，很难描述为 $u,v$ 的形式，因为需要出现两个子树为 $1$ 或者根节点被选择才能转移到 $2$。所以考虑记录辅助状态 $3$ 表示出现过至少 $2$ 次 $1$ 的方案。那么转移有以下 $8$ 种：

$$(0,0)\rightarrow 0$$ $$(0,1)\rightarrow 1 \ \ (1,0)\rightarrow 1$$ $$(0,2)\rightarrow 2 \ \ (2,0)\rightarrow 2$$ $$(3,0)\rightarrow 3 \ \ (3,1)\rightarrow 3$$ $$(1,1)\rightarrow 3$$

上面没有出现过的转移为不合法或者不存在对应状态。这么转移之后再考虑和根节点是否选择合并的转移，那么有：

$$(0,0)\rightarrow 0 \ \ (1,0)\rightarrow 1 \ \ (2,0)\rightarrow 2 \ \ (3,0)\rightarrow 3 \ \ $$$$(0,1)\rightarrow 3 \ \ (1,1)\rightarrow3 \ \ (3,1)\rightarrow 3 \ \ $$

转移的同时计入 $p,a$ 两个数组的贡献。最后将 $3$ 状态放到 $1,2$ 两种状态即可。因为 $3$ 状态对应的状态可以封口也可以不封口。复杂度 $O(n)$。

考虑对于 $k\neq 1$ 的情况，每一位暴力枚举上面的 $8$ 种转移，第一部分的转移复杂度是 $O(8^k)$ 的。对于复合根节点情况的部分，暴力枚举根节点状态显然不优，可以类似 FMT 的对每一位依次进行变换，也就是逐位枚举根节点状态并处理这一位变换后的位置。复杂度为 $O(k4^k)$。对于 $3$ 状态的下放可以用类似的做法也做到 $O(k4^k)$。复杂度 $O(n(8^k+k4^k))$，视常数可以获得 $45\sim 85$ 分。

考虑优化，目前的瓶颈在于 $O(8^k)$ 的部分。一个很神秘的做法是考虑到如果没有辅助状态 $3$，那么转移只有 $O(5^k)$。所以考虑枚举儿子的一些位置的状态钦定为 $3$，由于对于 $3$ 的转移是和 $0/1$ 复合之后仍然为 $3$，所以为 $3$ 的位可以让它的值为对应位为 $0/1$ 的和。类似 OR 卷积的 FWT，经过一次正变换之后为 $3$ 的位置真实值可以为 $0$ 或 $1$。然后对变换之后的部分进行 $O(5^k)$ 的转移，但是多了 $3$ 的状态，由于经过了变换，只需要加入 $(3,3)\rightarrow 3$ 的转移。这部分转移的复杂度是 $O(6^k)$ 的。对于转移之后 $3$ 的位置，他们是从 $(0/1,0/1)$ 转移过来的，所以真实值可能是 $0/1/3$，所以要进行一次类似 OR 卷积的 IFWT 让他变成真实值为 $3$ 的值。FWT 和 IFWT 的复杂度是 $O(k4^k)$，所以总的复杂度就是 $O(n(6^k+k4^k))$，可以通过。

#include<bits/stdc++.h>
using namespace std;
struct edge{int v,nxt;}e[205];
int n,m,u,v,cnt,h[105],w[105][256],p[105][8],dp[105][1<<16],num,tmp[1<<16];
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
struct node{int x,y,z;}go[2000005];
void init(int k,int x,int y,int z)
{
	if(k==m){go[++num]={x,y,z};return;}
	init(k+1,x,y,z);
	init(k+1,x,y|(1<<(k<<1)),z|(1<<(k<<1)));
	init(k+1,x|(1<<(k<<1)),y,z|(1<<(k<<1)));
	init(k+1,x|(2<<(k<<1)),y,z|(2<<(k<<1)));
	init(k+1,x,y|(2<<(k<<1)),z|(2<<(k<<1)));
	init(k+1,x|(3<<(k<<1)),y|(3<<(k<<1)),z|(3<<(k<<1)));
}
void fwt(int *a)
{
	for(int i=0;i<m;i++)
	{
		for(int s=0;s<(1<<(m<<1));s++)
		{
			int c=(s>>(i<<1))&3;
			if(c==0)Add(a[s+(3<<(i<<1))],a[s]);
			else if(c==1)Add(a[s+(2<<(i<<1))],a[s]); 
		}
	}
}
void ifwt(int *a)
{
	for(int i=0;i<m;i++)
	{
		for(int s=0;s<(1<<(m<<1));s++)
		{
			int c=(s>>(i<<1))&3;
			if(c==3)Add(a[s],mod-a[s-(3<<(i<<1))]),Add(a[s],mod-a[s-(2<<(i<<1))]);
		}
	}
}
void dfs(int u,int fa)
{
	dp[u][0]=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);
		for(int s=0;s<(1<<(m<<1));s++)tmp[s]=dp[u][s],dp[u][s]=0;
		fwt(tmp);fwt(dp[v]);
		for(int s=1;s<=num;s++)Add(dp[u][go[s].z],1ll*tmp[go[s].x]*dp[v][go[s].y]%mod);
		ifwt(dp[u]);
	}
	for(int i=0;i<m;i++)
	{
		for(int s=0;s<(1<<(m<<1));s++)tmp[s]=dp[u][s],dp[u][s]=0;
		for(int s=0;s<(1<<(m<<1));s++)
		{
			int c=(s>>(i<<1))&3;
			if(c==0)
			{
				Add(dp[u][s],1ll*tmp[s]*(mod+1-p[u][i])%mod);
				Add(dp[u][s|(3<<(i<<1))],1ll*tmp[s]*p[u][i]%mod);
			}
			else if(c==1)
			{
				Add(dp[u][s],1ll*tmp[s]*(mod+1-p[u][i])%mod);
				Add(dp[u][s|(2<<(i<<1))],1ll*tmp[s]*p[u][i]%mod);
			}
			else if(c==2)
			{
				Add(dp[u][s],1ll*tmp[s]*(mod+1-p[u][i])%mod);
			}
			else 
			{
				Add(dp[u][s],tmp[s]);
			}
		}
	}
	for(int s=0;s<(1<<(m<<1));s++)
	{
		int ns=0;
		for(int i=0;i<m;i++)if((s>>(i<<1))&1)ns|=(1<<i);
		dp[u][s]=1ll*dp[u][s]*w[u][ns]%mod;
	}
	for(int i=0;i<m;i++)
	{
		for(int s=0;s<(1<<(m<<1));s++)tmp[s]=dp[u][s],dp[u][s]=0;
		for(int s=0;s<(1<<(m<<1));s++)
		{
			if(((s>>(i<<1))&3)==3)
			{
				Add(dp[u][s-(1<<(i<<1))],tmp[s]);
				Add(dp[u][s-(2<<(i<<1))],tmp[s]); 
			}
			else Add(dp[u][s],tmp[s]);
		}
	}
}
int main()
{
	//freopen("e.in","r",stdin);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=0;i<m;i++)for(int j=1;j<=n;j++)cin>>p[j][i];
	for(int i=1;i<=n;i++)
	{
		for(int s=0;s<(1<<m);s++)cin>>w[i][s];
	}
	init(0,0,0,0);dfs(1,0);
	int ans=0;
	for(int s=0;s<(1<<(m<<1));s++)
	{
		int flag=1;
		for(int i=0;i<m;i++)flag&=(((s>>(i<<1))&3)!=1);
		if(flag)Add(ans,dp[1][s]);
	}
	cout<<ans;
	return 0;
}