No.1124 Earthquake Safety
Problem Statement
ABC City consists of $N$ houses and $N-1$ roads. The houses are numbered $1, 2, 3, ..., N$.
The $i$-th road connects houses $A_i$ and $B_i$, and any 2 houses are connected via some roads.
ABC City has many cliffs, so when an earthquake occurs, landslides cut off some of the roads.
Now, AGC, the mayor of ABC City, defined the safety level of the city $S$ as follows in order to examine its safety against earthquakes.
- Let $D_i$ be the number of houses reachable from house $i$ using only roads that have not been cut off (including house $i$ itself).
- Let $S = \left(D_{1}\right)^2 + \left(D_{2}\right)^2 + \left(D_{3}\right)^2 + ... + \left(D_{N}\right)^2$.
Since the answer can be very large, output it modulo $1 \ 000 \ 000 \ 007$.
Input
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$A_3$ $B_3$
$\hspace{4pt} : \hspace{12pt} :$
$A_{N-1}$ $B_{N-1}$
The input is given over $N$ lines.
On line $1$, the integer $N$ is given.
On line $1+i$ $(1 \leq i \leq N-1)$, the integers $A_i$, $B_i$ are given, separated by a space.
Output
Output, on $1$ line, the sum of the safety levels of the city modulo $1 \ 000 \ 000 \ 007$.
Constraints
- $1 \leq N \leq 300 \ 000$
- $1 \leq A_i < B_i \leq N$
- Any 2 houses are connected via some roads.
- All input values are integers.
Sample
Sample 1
Input
3 1 2 2 3
Output
48
Consider the following $4$ cases.
- No road is cut off: $D_1 = 3, D_2 = 3, D_3 = 3$, and the safety level of the city is $3^{2} + 3^{2} + 3^{2} = 27$.
- Road $1$ is cut off: $D_1 = 1, D_2 = 2, D_3 = 2$, and the safety level of the city is $1^{2} + 2^{2} + 2^{2} = 9$.
- Road $2$ is cut off: $D_1 = 2, D_2 = 2, D_3 = 1$, and the safety level of the city is $2^{2} + 2^{2} + 1^{2} = 9$.
- All roads are cut off: $D_1 = 1, D_2 = 1, D_3 = 1$, and the safety level of the city is $1^{2} + 1^{2} + 1^{2} = 3$.
Sample 2
Input
4 1 2 2 3 3 4
Output
170
In this problem, roads arranged in a straight line are dangerous.
Sample 3
Input
4 1 2 1 3 1 4
Output
182
The number of houses is the same as in "Sample 2", but this one is safer against earthquakes.
Sample 4
Input
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10
Output
61424
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
e869120
QCFium