問題一覧 > 通常問題

No.828 All-Direction Prodigy Number

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : Pachicobue / テスター : kopricky
お気に入りにしたユーザー ProblemId : 2977 / 自分の提出
問題文最終更新日: 2021-12-08 04:48:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 213 (順位表) の他の問題:

Problem Statement

Aoki obtained a tree $T$ consisting of vertices $1,2,...,N$. Each vertex $i$ of $T$ already has the value $i$ written on it.
Aoki decided to play with the tree $T$ by regarding it as a rooted tree.

For a rooted tree, Aoki decided to call vertex $i$ a prodigy when "vertex $i$ has a value written on it that is greater than the value of every ancestor of vertex $i$ (excluding itself)". However, the root is always a prodigy.
He also defined the prodigy number as how many of the $N$ vertices are prodigies.
(Note that whether each vertex is a prodigy depends on which vertex is taken as the root.)
For example, consider the rooted tree in the figure below. The yellow vertices are prodigies, and the prodigy number is 4.
Here, the vertex with the value $6$ written on it is a prodigy, because its ancestors have the values $\{3,1\}$ written on them, which contain only values less than $6$.
On the other hand, the vertex with the value $4$ written on it is not a prodigy, because its ancestors have the values $\{3,7\}$ written on them, which contain a value greater than $4$.

Aoki noticed that the prodigy number of $T$ depends on the choice of the root,
and he has asked you what the prodigy number $S_i$ is when vertex $i (i=1,2,...,N)$ is taken as the root.
Since telling him many numbers would be troublesome, you decided to use a sequence $r=\{r_1,r_2,...,r_N\}$ and tell him $(r_1+S_1)\times(r_2+S_2)\times ...\times(r_N+S_N)$.
However, since this value can be very large, tell him the remainder when it is divided by $10^9+7$.

Input

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

The first line contains the number of vertices $N$ of the tree.
The second line contains the $N$ elements of the sequence $r$ used to compute the answer, separated by spaces.
Each of the third through $N+1$-th lines contains integers $u, v$ representing the endpoints of an edge of the tree $T$, separated by a space. This means that vertices $u, v$ are connected bidirectionally.
* Note that the input is rather large.

Constraints
  • $1 \le N \le 2\times 10^5$
  • $0 \le r_i \lt 10^9+7$
  • $1 \le u_i,v_i \le N$
  • The input graph is a tree with $N$ vertices.
  • All inputs are integers.

Output

Print the remainder when $\prod_{i=1}^N(r_i+S_i)$ is divided by $10^9+7$ on one line.
Print a newline at the end.

Sample

Sample 1
Input
3
0 0 0
1 2
2 3
Output
6

The figure below shows the tree with each of vertices 1,2,3 regarded as the root. The vertices painted yellow are prodigies.

Sample 2
Input
3
0 0 0
1 3
3 2
Output
4

The figure below shows the tree with each of vertices 1,2,3 regarded as the root. The vertices painted yellow are prodigies.

Sample 3
Input
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
Output
598344873

Be careful to answer with the remainder modulo $10^9+7$.

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