問題一覧 > 通常問題

No.828 全方位神童数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : Pachicobue / テスター : kopricky
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)を根としたときの神童数Siがいくつになるのか、あなたに尋ねてきました。
たくさんの数を伝えるのは大変なので、数列r={r1,r2,...,rN}を用いて、(r1+S1)×(r2+S2)×...×(rN+SN) を教えてあげることにしました。
但しこの値は非常に大きくなりうるので、109+7で割った余りを教えてあげて下さい。

入力

N 
r1 r2 ... rN
u1 v1
u2 v2

uN1 vN1

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

制約
  • 1N2×105
  • 0ri<109+7
  • 1ui,viN
  • 入力されるグラフはN頂点の木である。
  • 入力は全て整数である。

出力

i=1N(ri+Si)109+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

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

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