問題一覧 > 通常問題

No.1124 Earthquake Safety

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : e869120 / テスター : QCFium
お気に入りにしたユーザー ProblemId : 4634 / 自分の提出
問題文最終更新日: 2020-07-17 23:25:09
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 258 (順位表) の他の問題:

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 there are $N-1$ roads, there are $2^{N-1}$ ways in which the roads can be cut off. Find the sum of the safety levels of the city over all of these cases.
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$.
Therefore, the sum of the safety levels of the city is $27 + 9 + 9 + 3 = 48$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。