No.828 All-Direction Prodigy Number
タグ : / 解いたユーザー数 24
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。