题目描述
A 省总共有 $n$ 座城市，城市之间由 $n-1$ 条道路连通，构成一颗树。
第 $i$ 座城市具有一个非负整数的魅力值 $w_i$，对于一个由城市构成的连通块 $S$ 满足这些城市的魅力值平均为 $1$，也即 $\dfrac{1}{|S|}\sum_{u\in S}w_u=1$，我们称这个连通块是和谐的。
现在我们并不知道每座城市具体的魅力值，只知道第 $i$ 座城市的魅力值一定是 $0$ 到 $a_i-1$ 间均匀随机的一个整数。
试问，A 省期望有多少个城市构成的连通块是和谐的？你只需要输出期望乘以 $\prod_{i=1}^n(a_i+1)$ 的答案，由于答案可能很大，你只需要输出对它取模 $998244353$ 的结果。
输入格式
第一行输入一个正整数 $n$，表示城市的数量。
第二行输入 n 个正整数，依次表示 $a_i$。
接下来 $n-1$ 行每行输入两个正整数 $u,v$，表示一条边。
输出格式
输出一行一个整数，表示答案。
样例输入 #1
2
1 2
1 2样例输出 #1
7样例输入 #2
3
2 1 3
1 2
1 3样例输出 #2
46样例解释 1
- 当 $w_1=1$ 时，$\text{{1}}$ 是和谐的，这有 $\dfrac{1}{2}$ 的概率发生。
- 当 $w_2=1$ 时，$\text{{2}}$ 是和谐的，这有 $\dfrac{1}{3}$ 的概率发生。
- 当 $w_1=w_2=1$ 或 $w_1=0,w_2=2$ 时，$\text{{1,2}}$ 是和谐的，这有 $\dfrac{1}{3}$ 的概率发生。
因此，总共期望有 $\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{3}=\dfrac{7}{6}$ 个和谐的连通块。
数据范围
对于 $100\text{%}$ 的数据，保证 $1\le n\le 3000$。对于所有 $1\le i\le n$，有 $1\le a_i\le n$，输入的 $u,v$ 保证构成一颗树。
对于测试点 $\text{1~3}$，保证 $n\le 50$。
对于测试点 $\text{4~5}$，保证 $\sum a_i\le 5000$。
对于测试点 $\text{6~7}$，保证树是一条链，且 $v=u+1$。
对于测试点 $8$，保证 $a_i=n$。
对于测试点 $\text{9~10}$，没有特殊限制。