数字积木
题号：NC296736
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

数字积木
\hspace{15pt}Bingbong 给定一棵包含 n 个节点的积木树，树的节点编号为 1\sim n，节点 i 的权值为 a_i，其中 a 由 0\sim n-1 的数字组成，且每个数字只出现一次。
\hspace{15pt}定义树上一个连通子图的权值为：构成该连通子图的所有节点的权值中未出现过的最小非负整数。
\hspace{15pt}现在，Bingbong 想让你帮忙计算树上所有连通子图的权值之和。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。\hspace{15pt}
\hspace{15pt}
【名词解释】
\hspace{15pt}连通子图：满足是原图的一个子图，连通子图内的任意两个顶点之间都存在路径相连，且路径上的点也在连通子图内；单独的点也构成一个连通子图。

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(1\leq n\leq 2\times 10^5\right)，表示树的结点个数。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(0\leq a_i\leq n-1\right)，保证每个整数恰好出现一次。
\hspace{15pt}此后 n-1 行，第 i 行输入两个整数 u_i,v_i\left(1\leq u_i,v_i\leq n;\, u_i\neq v_i\right)，表示第 i 条树边连接节点 u_i 和 v_i。

输出描述:

\hspace{15pt}输出一个整数，表示树上所有连通子图的权值之和对 (10^9+7) 取模后的结果。
示例1

输入

复制 
2
0 1
1 2

输出

复制 
3
示例2

输入

复制 
5
1 4 3 0 2
1 2
1 3
2 4
2 5

输出

复制 
15