F - Distributing Integers Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの番号が付けられた N 個の頂点を持つ木があります。この木の i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。
k=1,...,N に対して、以下の問題を解いてください。

  • 以下の手順に従って,木の各頂点に整数を書くことを考える。
    • まず、頂点 k に 1 を書く。
    • 2,...,N を順番に頂点に書く。書き込む頂点は、次のように決める。
      • まだ整数が書かれていない頂点であって、整数が書かれた頂点に隣接しているものを選ぶ。このような頂点が複数存在する場合は、その中からランダムに選ぶ。
  • 整数の書き方として考えられるものの数を 10^9+7 で割ったあまりを求めよ。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq a_i,b_i \leq N
  • 与えられるグラフは木である

入力

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

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

出力

k=1,2,...,N に対する問題の答えを、順番に一行に出力せよ。

入力例 1

3
1 2
1 3

出力例 1

2
1
1

この入力中のグラフは以下のようなものです。

図

k=1 に対する問題において、以下のように 2 通りの整数の書き方が考えられます。

  • 頂点 1,2,3 に、それぞれ 1,2,3 を書く
  • 頂点 1,2,3 に、それぞれ 1,3,2 を書く

入力例 2

2
1 2

出力例 2

1
1

この入力中のグラフは以下のようなものです。

図

入力例 3

5
1 2
2 3
3 4
3 5

出力例 3

2
8
12
3
3

この入力中のグラフは以下のようなものです。

図

入力例 4

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

出力例 4

40
280
840
120
120
504
72
72

この入力中のグラフは以下のようなものです。

図

Score : 600 points

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i. For each k=1, ..., N, solve the problem below:

  • Consider writing a number on each vertex in the tree in the following manner:
    • First, write 1 on Vertex k.
    • Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:
      • Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.
  • Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7).

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq a_i,b_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

For each k=1, 2, ..., N in this order, print a line containing the answer to the problem.

Sample Input 1

3
1 2
1 3

Sample Output 1

2
1
1

The graph in this input is as follows:

Figure

For k=1, there are two ways in which we can write the numbers on the vertices, as follows:

  • Writing 1, 2, 3 on Vertex 1, 2, 3, respectively
  • Writing 1, 3, 2 on Vertex 1, 2, 3, respectively

Sample Input 2

2
1 2

Sample Output 2

1
1

The graph in this input is as follows:

Figure

Sample Input 3

5
1 2
2 3
3 4
3 5

Sample Output 3

2
8
12
3
3

The graph in this input is as follows:

Figure

Sample Input 4

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

Sample Output 4

40
280
840
120
120
504
72
72

The graph in this input is as follows:

Figure