树上 MEX 问题

Problem Description

定义一张图的 MEX 为：在图中所有点的点权所构成的集合中，最小的没有出现过的非负整数。 给定一棵 $n$ 个点的树，点编号为 $1$ 到 $n$，第 $i$ 个点有点权 $a_i$，保证每个点的点权互不相同。求这棵树的所有 连通导出子图 的 MEX 之和，答案对 $998244353$ 取模。 一个图的导出子图是指，由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图。

Input

第一行一个正整数 $T$（$1\le T\le 10^5$），表示测试数据组数。 对于每组数据，第一行包含一个整数 $n$（$1\le n\le 10^5$），表示树的点数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots ,a_n$（$0\le a_i < n$），表示每个点的点权。保证每个点的点权互不相同。 接下来 $n-1$ 行描述了这棵树，每行包含两个整数 $u,v$（$1\le u,v\le n$），表示点 $u$ 和点 $v$ 之间有一条边。保证输入是一棵树。 保证对于所有测试数据，$n$ 之和不超过 $10^6$。

Output

对于每组测试数据，输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

Sample Input

3
6
0 1 2 3 4 5
1 2
1 3
3 4
3 5
2 6
6
1 2 3 4 5 0
1 2
1 3
3 4
3 5
2 6
6
2 3 4 5 0 1
1 2
1 3
3 4
3 5
2 6

Sample Output

40
24
18

Source

2024“钉耙编程”中国大学生算法设计超级联赛（6）