問題一覧 > 通常問題

No.1124 Earthquake Safety

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : e869120e869120 / テスター : QCFiumQCFium
6 ProblemId : 4634 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-07-17 23:25:09

問題文

ABC 市は $N$ 軒の家と $N-1$ 本の道路からなる。家は $1, 2, 3, ..., N$ と番号付けられている。
$i$ 本目の道路は家 $A_i$ と $B_i$ を繋いでおり、どの 2 つの家の間もいくつかの道路を介して繋がっている。

ABC 市は崖が多いため、地震が起こると、崖崩れによりいくつかの道路が寸断される。
さて、ABC 市長である AGC さんは、地震に対する安全性を調べるため、市の安全度 $S$ を以下のように定義した。

  • $D_i$ を、家 $i$ から寸断されていない道のみを通じて行くことができる家の個数とする。（家 $i$ 自身を含む）
  • $S = \left(D_{1}\right)^2 + \left(D_{2}\right)^2 + \left(D_{3}\right)^2 + ... + \left(D_{N}\right)^2$ とする。
道路は $N-1$ 本あるので、道路の寸断のされ方は $2^{N-1}$ 通りある。それら全ての場合における、市の安全度の総和を求めよ。
答えは非常に大きくなることがあるため、$1 \ 000 \ 000 \ 007$ で割った余りを出力せよ。

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$A_3$ $B_3$
$\hspace{4pt} : \hspace{12pt} :$
$A_{N-1}$ $B_{N-1}$

$N$ 行に渡る入力が与えられる。
$1$ 行目に、整数 $N$ が与えられる。
$1+i$ $(1 \leq i \leq N-1)$ 行目に、整数 $A_i$, $B_i$ が空白区切りで与えられる。

出力

$1$ 行に、市の安全度の総和を $1 \ 000 \ 000 \ 007$ で割った余りを出力しなさい。

制約

  • $1 \leq N \leq 300 \ 000$
  • $1 \leq A_i < B_i \leq N$
  • どの 2 つの家の間も、いくつかの道路を介して繋がっている。
  • 入力はすべて整数

サンプル

サンプル1
入力
3
1 2
2 3
出力
48

以下の $4$ 通りの場合を考える。

  • どの道路も寸断されない場合： $D_1 = 3, D_2 = 3, D_3 = 3$ となり、市の安全度は $3^{2} + 3^{2} + 3^{2} = 27$ となる。
  • 道路 $1$ が寸断される場合： $D_1 = 1, D_2 = 2, D_3 = 2$ となり、市の安全度は $1^{2} + 2^{2} + 2^{2} = 9$ となる。
  • 道路 $2$ が寸断される場合： $D_1 = 2, D_2 = 2, D_3 = 1$ となり、市の安全度は $2^{2} + 2^{2} + 1^{2} = 9$ となる。
  • 全ての道路が寸断される場合： $D_1 = 1, D_2 = 1, D_3 = 1$ となり、市の安全度は $1^{2} + 1^{2} + 1^{2} = 3$ となる。
よって、市の安全度の総和は $27 + 9 + 9 + 3 = 48$ となる。

サンプル2
入力
4
1 2
2 3
3 4
出力
170

この問題の場合、直線状の道路は危険である。

サンプル3
入力
4
1 2
1 3
1 4
出力
182

「サンプル2」と家の数が同じだが、こちらの方が地震に対しては安全である。

サンプル4
入力
10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
出力
61424

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