好神仙的题目。赛时胡了一个状态和转移都和官解不同的做法，得到了 \(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;
}