問題一覧 > 通常問題

No.828 全方位神童数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : PachicobuePachicobue / テスター : koprickykopricky
4 ProblemId : 2977 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-08 04:48:34

問題文

青木くんは 頂点$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$での余りを答えることに気をつけて下さい。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。