[Solution] Tree Coloring solution codeforces

Tree Coloring solution codeforces

You are given a rooted tree consisting of 𝑛n vertices numbered from 11 to 𝑛n. The root of the tree is the vertex 11.

You have to color all vertices of the tree into 𝑛n colors (also numbered from 11 to 𝑛n) so that there is exactly one vertex for each color. Let 𝑐𝑖ci be the color of vertex 𝑖i, and 𝑝𝑖pi be the parent of vertex 𝑖i in the rooted tree. The coloring is considered beautiful if there is no vertex 𝑘k (𝑘>1k>1) such that 𝑐𝑘=𝑐𝑝𝑘1ck=cpk−1, i. e. no vertex such that its color is less than the color of its parent by exactly 11.

Calculate the number of beautiful colorings, and print it modulo 998244353998244353.

Input

The first line contains one integer 𝑛n (2𝑛2500002≤n≤250000) — the number of vertices in the tree.

Then 𝑛1n−1 lines follow, the 𝑖i-th line contains two integers 𝑥𝑖xi and 𝑦𝑖yi (1𝑥𝑖,𝑦𝑖𝑛1≤xi,yi≤n𝑥𝑖𝑦𝑖xi≠yi) denoting an edge between the vertex 𝑥𝑖xi and the vertex 𝑦𝑖yi. These edges form a tree.

Output

Print one integer — the number of beautiful colorings, taken modulo 998244353998244353.

Examples Tree Coloring solution codeforces

input v Tree Coloring solution codeforces

Copy Tree Coloring solution codeforces
5
1 2
3 2
4 2
2 5

output

Copy
42

input

Copy
5
1 2
2 3
3 4
4 5

output

Copy
53

input

Copy
20
20 19
20 4
12 4
5 8
1 2
20 7
3 10
7 18
11 8
9 10
17 10
1 15
11 16
14 11
18 10
10 1
14 2
13 17
20 6

output

Copy
955085064

The One Where They Get Back Together solution codechefMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcode

Leave a Comment

Your email address will not be published. Required fields are marked *