E - Black Cats Deployment

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

すぬけフェスティバル2017が 1,2, ...,N の番号がついた N 頂点の木で開催されます。 この木の i 番目の辺は頂点 a_i と b_i をつなぐ楽しさ c_i の辺です。

すぬけくんと N-1 匹の黒猫がスタッフです。 すぬけくんはある頂点に本部を設置し、それ以外の N-1 個の頂点にそれぞれ黒猫を 1 匹派遣しようと考えています。

全ての頂点について、その頂点に本部を設置したときの 良さ を計算してください。 頂点 i に本部を置いたときの良さは以下のようにして計算されます。

  • X=0 とする
  • 1 以上 N 以下の整数 j (ただし i を除く)について、以下の処理を行う
    • 頂点 i から頂点 j への経路の途中にある辺のうち、最も楽しさが小さいような辺の楽しさ c を X に加算する
  • 最終的な X の値が良さである

制約

  • 1 \leq N \leq 10^{5}
  • 1 \leq a_i,b_i \leq N
  • 1 \leq c_i \leq 10^{9}
  • 与えられるグラフは木
  • 与えられる入力は全て整数

部分点

  • 200 点分のデータセットでは N \leq 1000 が成立する
  • 200 点分のデータセットでは c_i \leq 2 が成立する

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}

出力

N 行に答えを出力せよ。 i 行目には頂点 i に本部を設置したときの良さを出力せよ。

入力例 1

3
1 2 10
2 3 20

出力例 1

20
30
30
  • 以下の図に頂点 1,2,3 に本部を設置した場合をそれぞれ示します
  • 辺の上に書かれた数はその辺の楽しさを、頂点の下に書かれた数は本部からその頂点への経路の途中にある辺のうち、最も楽しさが小さいような辺の楽しさを示します
1ee10aa2a1bf5e43e05161f37d88bdc1.png

入力例 2

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2

出力例 2

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20

入力例 3

19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14

出力例 3

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370

Score : 800 points

Problem Statement

Snuke Festival 2017 will be held in a tree with N vertices numbered 1,2, ...,N. The i-th edge connects Vertex a_i and b_i, and has joyfulness c_i.

The staff is Snuke and N-1 black cats. Snuke will set up the headquarters in some vertex, and from there he will deploy a cat to each of the other N-1 vertices.

For each vertex, calculate the niceness when the headquarters are set up in that vertex. The niceness when the headquarters are set up in Vertex i is calculated as follows:

  • Let X=0.
  • For each integer j between 1 and N (inclusive) except i, do the following:
    • Add c to X, where c is the smallest joyfulness of an edge on the path from Vertex i to Vertex j.
  • The niceness is the final value of X.

Constraints

  • 1 \leq N \leq 10^{5}
  • 1 \leq a_i,b_i \leq N
  • 1 \leq c_i \leq 10^{9}
  • The given graph is a tree.
  • All input values are integers.

Partial Scores

  • In the test set worth 200 points, N \leq 1000.
  • In the test set worth 200 points, c_i \leq 2.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}

Output

Print N lines. The i-th line must contain the niceness when the headquarters are set up in Vertex i.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

20
30
30
  • The figure below shows the case when headquarters are set up in each of the vertices 1, 2 and 3.
  • The number on top of an edge denotes the joyfulness of the edge, and the number below an vertex denotes the smallest joyfulness of an edge on the path from the headquarters to that vertex.
1ee10aa2a1bf5e43e05161f37d88bdc1.png

Sample Input 2

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2

Sample Output 2

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20

Sample Input 3

19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14

Sample Output 3

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370
F - Unicyclic Graph Counting

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

すぬけくんは以下のような問題を考えました。

長さ N の数列 d が与えられます。 以下の条件を満たす頂点に 1,2,...,N のラベルがついた N 頂点の無向グラフの数を modulo 10^{9} + 7 で求めてください。

  • グラフは単純かつ連結
  • 頂点 i の次数は d_i

　2 \leq N, 1 \leq d_i \leq N-1, {\rm Σ} d_i = 2(N-1) を満たす場合 には、この問題の答えは \frac{(N-2)!}{(d_{1} -1)!(d_{2} - 1)! ... (d_{N}-1)!} で表せることが証明できます。

すぬけくんは 3 \leq N, 1 \leq d_i \leq N-1, { \rm Σ} d_i = 2N を満たす場合 どうなるかが気になっています。 すぬけくんの代わりにこの問題を解いてください。

制約

  • 3 \leq N \leq 300
  • 1 \leq d_i \leq N-1
  • { \rm Σ} d_i = 2N

部分点

  • 200 点分のデータセットでは N \leq 5 が成立する
  • 別の 200 点分のデータセットでは N \leq 18 が成立する
  • 別の 300 点分のデータセットでは N \leq 50 が成立する

入力

入力は以下の形式で標準入力から与えられる。

N
d_1 d_2 ... d_{N}

出力

答えを出力せよ。

入力例 1

5
1 2 2 3 2

出力例 1

6
  • 以下の図に示されるような 6 通りです
51367cdb21c64bfb07113b300921d52c.png

入力例 2

16
2 1 3 1 2 1 4 1 1 2 1 1 3 2 4 3

出力例 2

555275958
  • 10^{9} + 7 で割ったあまりを求めてください

Score : 1000 points

Problem Statement

Snuke has come up with the following problem.

You are given a sequence d of length N. Find the number of the undirected graphs with N vertices labeled 1,2,...,N satisfying the following conditions, modulo 10^{9} + 7:

  • The graph is simple and connected.
  • The degree of Vertex i is d_i.

When 2 \leq N, 1 \leq d_i \leq N-1, {\rm Σ} d_i = 2(N-1), it can be proved that the answer to the problem is \frac{(N-2)!}{(d_{1} -1)!(d_{2} - 1)! ... (d_{N}-1)!}.

Snuke is wondering what the answer is when 3 \leq N, 1 \leq d_i \leq N-1, { \rm Σ} d_i = 2N. Solve the problem under this condition for him.

Constraints

  • 3 \leq N \leq 300
  • 1 \leq d_i \leq N-1
  • { \rm Σ} d_i = 2N

Partial Scores

  • In the test set worth 200 points, N \leq 5.
  • In the test set worth another 200 points, N \leq 18.
  • In the test set worth another 300 points, N \leq 50.

Input

Input is given from Standard Input in the following format:

N
d_1 d_2 ... d_{N}

Output

Print the answer.

Sample Input 1

5
1 2 2 3 2

Sample Output 1

6
  • There are six graphs as shown below:
51367cdb21c64bfb07113b300921d52c.png

Sample Input 2

16
2 1 3 1 2 1 4 1 1 2 1 1 3 2 4 3

Sample Output 2

555275958
  • Be sure to find the answer modulo 10^{9} + 7.