問題一覧 > 通常問題

No.827 総神童数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 : PachicobuePachicobue / テスター : koprickykopricky
12 ProblemId : 2978 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-05-02 18:41:29

問題文

青木くんは 頂点$1,2,...,N$ からなる根付き木 $T$ を手に入れました。$T$ の根は頂点$1$ です。
青木くんは根付き木 $T$ の各頂点に $1,2,...,N$ の値を重複無く書き込む事を考えています。
つまり頂点$i$ に書き込まれた値を $c_i$ とするとき、 数列$\{c_i\}$ が $\{1,2,...,N\}$ の順列であるようにします。

青木くんは、「頂点$i$ に、頂点$i$の(自分を除く)どの先祖の値よりも大きな値が書き込まれている」とき、頂点$i$ を神童と呼ぶことに決めました。但し根は必ず神童であるとします。
また $N$頂点のうち、いくつが神童であるかを神童数と定義しました。
例えば下図のような値の書き込み方を考えると、黄色の頂点が神童であり、神童数は4となります。
ここで $6$の値が書き込まれた頂点は神童です。なぜなら先祖に$\{3,1\}$の値が書き込まれており、$6$未満の値しか含まれないからです。
また $4$の値が書き込まれた頂点は神童ではありません。なぜなら先祖に$\{3,7\}$の値が書き込まれており、$4$よりも大きな値が含まれるからです。

青木くんは根付き木$T$ がいかに優秀な木か気になり、 値の書き込み方$N!$ 通り全てを試した場合に神童数の合計はいくつになるか尋ねてきました。
あなたの仕事はこの答えを青木くんの代わりに計算することです。 但しこの値は非常に大きくなりうるので、$10^9+7$ で割った余りで教えてあげて下さい。

入力

$N$ 
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$

1行目に木の頂点数$N$ が与えられます。
2行目から$N$行目までには、木$T$ の辺の端点を表す整数 $u, v$ が空白区切りで与えられます。これは頂点$u, v$が双方向に結ばれていることを意味します。

制約
  • $1 \le N \le 2\times 10^5$
  • $1 \le u_i,v_i \le N$
  • 入力されるグラフは$N$頂点の木である。
  • 入力は全て整数である。

出力

$T$への値の書き込み方$N!$通り全てに対する、神童数の総和を$10^9+7$で割った余りを一行に出力して下さい。
最後に改行して下さい。

サンプル

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

値の書き込み方は以下の2通りあり、黄色の頂点が神童です。
右で1が書かれた頂点は、親の値が2であり自分の値より大きいので神童ではありません。

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

値の書き込み方は以下の6通りあり、黄色の頂点が神童です。

サンプル3
入力
20
2 15
6 5
12 1
7 9
17 2
15 5
2 4
17 16
12 2
8 17
17 19
18 11
20 8
20 3
13 9
11 10
11 20
14 8
11 7
出力
820010006

$10^9+7$ で余りを取ることに注意して下さい。

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