因为是普及组模拟，所以没有背景。

题目描述

给出一棵$n$个节点的树，节点标号为$1$到$n$，第$i$个点有点权$w_i$。

定义一个点的集合的能量值是集合中所有点点权和的平方。

现在你要求出树上所有连通块的能量值的和。

树上一个点的集合是连通块，当且仅当只保留两个端点都在集合内的边后，该集合仍然连通。

由于答案可能很大，你只需要输出它模$998244353$的值。

输入格式

第一行一个正整数$n$，表示节点数目。

接下来一行$n$个整数$w_i$，表示第$i$个点的点权是$w_i$。

接下来$n-1$行，第$i$行两个正整数$u_i,v_i$，表示树上有一条$u_i$和$v_i$之间的边。

保证给出的边形成一棵树。

输出格式

一行一个整数，表示答案模$998244353$的值。

样例输入1

4
1 2 3 4
1 3
2 3
4 3

样例输出1

401

样例2

见下发文件的ex_tree2.in与ex_tree2.out。

数据范围

本题不采取子任务评测。

对于$20 \%$的数据，$n\leq 18$。

对于$30\%$的数据，$n\leq1000$。

对于另外$20\%$的数据，$\forall 2\leq i\leq n,w_i=0$。

对于另外$20\%$的数据，$u_i=i$，$v_i=i+1$。

对于$100\%$的数据，$1 \leq n\leq10^5$，$0 \leq w_i < 998244353$。

时间限制:1s

空间限制:512MB

本题下发文件