← 返回题目列表

Codeforces · 1613/F

F. 树着色

中文机器翻译题面 查看原题

给你一个有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。树的根是顶点$$$1$$$。

您必须将树的所有顶点着色为 $$$n$$$ 颜色(也编号从 $$$1$$$ 到 $$$n$$$),以便每种颜色恰好有一个顶点。设 $$$c_i$$$ 为顶点 $$$i$$$ 的颜色,$$$p_i$$$ 为有根树中顶点 $$$i$$$ 的父节点。如果没有顶点 $$$k$$$ ($$$k > 1$$$) 使得 $$$c_k = c_{p_k} - 1$$$,则着色被认为是漂亮的,i。 e.没有顶点的颜色比其父级的颜色精确 $$$1$$$。

计算美丽颜色的数量,并以 $$$998244353$$$ 为模打印。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250000$$$) — 树中的顶点数。

接下来是 $$$n-1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) 表示顶点 $$$x_i$$$ 和顶点$$$y_i$$$。这些边形成一棵树。

输出

打印一个整数 — 漂亮颜色的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

5
1 2
3 2
4 2
2 5

输出 #1

42

输入 #2

5
1 2
2 3
3 4
4 5

输出 #2

53

输入 #3

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

输出 #3

955085064