霜雪千年

题号：NC236764
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

枫红十里长街
红帘后谁人蹙着眉
遥梦桑竹桃源
轮回中曾道别的地点
愿今生再相见
消融你眉间
悲戚霜雪

世界由 $n$ 个国家组成，由 $n-1$ 条边连接且保证联通。 $m$ 年之中，在第 $i$ 年暴风雪会随机袭击 $a_i$ 个国家。

第 $i$ 个国家的抗寒能力为 $b_i$ ，如果这个国家连续 $b_i$ 年都被暴风雪袭击那么这个国家将会被冰封（但没有暴风雪的那一年会马上解冻）。

定义一年世界的混乱程度为所有未冰封国家组成的生成子图的联通块数量。

求世界 $m$ 年中每一年的混乱程度之和的期望值。

第一行输入两个正整数 $n,m$ $(1\leq n\leq 10^6,1\leq m\leq 1000)$ 。

接下来一行 $m$ 个正整数，第 $i$ 个数 $a_i$ $(1< a_i\leq n)$ 表示第 $i$ 年暴风雪会袭击的国家个数。

接下来一行 $n$ 个正整数，第 $i$ 个数 $b_i$ $(1\leq b_i\leq m)$ 表示第 $i$ 个国家的抗寒程度。

接下来 $n-1$ 行每行两个正整数 $x,y$ $(1\leq x,y\leq n)$ 表示有一条道路连接 $x$ 和 $y$ 两个国家。

输出一行一个正整数表示世界 $m$ 年中每一年的混乱程度之和的期望值，答案对 $998244353$ 取模。

保证答案可以表示为形如 $\frac{p}{q}$ 的形式（ $p,q\in N,q\neq 0$ ）的形式，而你需要输出 $p×q^{-1}$ 在模 $998244353$ 意义下的值。

示例1

复制

复制

示例2

复制

复制

887328316

示例3

复制

复制

471393169