No.828 全方位神童数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 17
作問者 : PachicobuePachicobue / テスター : koprickykopricky
4 ProblemId : 2977 / 出題時の順位表

問題文

青木くんは 頂点$1,2,...,N$ からなる木 $T$ を手に入れました。$T$ の各頂点$i$ には値$i$ が既に書き込まれています。
青木くんは木 $T$を根付き木とみなして遊ぶことにしました。

青木くんは根付き木に対して、「頂点$i$ に、頂点$i$の(自分を除く)どの先祖の値よりも大きな値が書き込まれている」とき、頂点$i$ を神童と呼ぶことに決めました。但し根は必ず神童であるとします。
また $N$頂点のうち、いくつが神童であるかを神童数と定義しました。
(各頂点が神童かどうかは、どの頂点を根とするかに依存することに注意して下さい)
例えば下図のような根付き木を考えると、黄色の頂点が神童であり、神童数は4となります。
ここで $6$の値が書き込まれた頂点は神童です。なぜなら先祖に$\{3,1\}$の値が書き込まれており、$6$未満の値しか含まれないからです。
また $4$の値が書き込まれた頂点は神童ではありません。なぜなら先祖に$\{3,7\}$の値が書き込まれており、$4$よりも大きな値が含まれるからです。

青木くんは$T$の神童数が根の取り方に依存することに気づき、
頂点$i (i=1,2,...,N)$を根としたときの神童数$S_i$がいくつになるのか、あなたに尋ねてきました。
たくさんの数を伝えるのは大変なので、数列$r=\{r_1,r_2,...,r_N\}$を用いて、$(r_1+S_1)\times(r_2+S_2)\times ...\times(r_N+S_N)$ を教えてあげることにしました。
但しこの値は非常に大きくなりうるので、$10^9+7$で割った余りを教えてあげて下さい。

入力

$N$ 
$r_1\ r_2\ ...\ r_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$

1行目に木の頂点数$N$が与えられます。
2行目には答えの計算に用いる数列$r$の$N$要素が空白区切りで与えられます。
3行目から$N+1$行目までには、木$T$ の辺の端点を表す整数 $u, v$ が空白区切りで与えられます。これは頂点$u, v$が双方向に結ばれていることを意味します。
※入力が多めなので注意して下さい。

制約
  • $1 \le N \le 2\times 10^5$
  • $0 \le r_i \lt 10^9+7$
  • $1 \le u_i,v_i \le N$
  • 入力されるグラフは$N$頂点の木である。
  • 入力は全て整数である。

出力

$\prod_{i=1}^N(r_i+S_i)$ を$10^9+7$で割った余りを一行に出力して下さい。
最後に改行して下さい。

サンプル

サンプル1
入力
3
0 0 0
1 2
2 3
出力
6

頂点1,2,3を根とみなした様子が以下の図です。黄色に塗られた頂点が神童です。

サンプル2
入力
3
0 0 0
1 3
3 2
出力
4

頂点1,2,3を根とみなした様子が以下の図です。黄色に塗られた頂点が神童です。

サンプル3
入力
20
397391841 679700971 145606697 977415091 513786611 99670444 666370425 151199845 823785563 113697511 311512752 592551093 141690528 337950684 441783513 543190271 462296398 851050627 141769971 473127767
17 19
18 11
19 6
20 8
8 16
20 3
13 9
11 10
15 8
11 20
17 18
14 8
1 20
2 5
11 7
11 4
5 20
1 12
2 13
出力
598344873

$10^9+7$での余りを答えることに気をつけて下さい。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。