← 返回题目列表

Codeforces · 1725/I

I. 模仿密钥树

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

Pak Chanek有一棵树,称为密钥树。该树由 $$$N$$$ 个顶点和 $$$N-1$$$ 个边组成。树的边从 $$$1$$$ 到 $$$N-1$$$ 编号,边 $$$i$$$ 连接顶点 $$$U_i$$$ 和 $$$V_i$$$。最初,密钥树的每条边都没有权重。

形式上,图中长度为 $$$k$$$ 的路径是一个序列 $$$[v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_k, e_k, v_{k+1}]$$$ ,使得:

- 对于每个 $$$i$$$,$$$v_i$$$ 是一个顶点,$$$e_i$$$ 是一条边。
- 对于每个 $$$i$$$,$$$e_i$$$ 连接顶点 $$$v_i$$$ 和 $$$v_{i+1}$$$。

电路是在同一顶点开始和结束的路径。

当且仅当路径不多次使用同一条边时,图中的路径才被称为简单路径。请注意,简单路径可以多次使用同一顶点。

加权图中简单路径的成本定义为其遍历的所有边的最大权重。

计算满足以下条件的不同无向加权图的数量:

- 该图有 $$$N$$$ 个顶点和 $$$2N-2$$$ 个边。
- 对于每对不同的顶点 $$$(x, y)$$$,存在一个穿过图中顶点 $$$x$$$ 和 $$$y$$$ 的简单电路。
- 图中每条边的权重是 $$$1$$$ 和 $$$2N-2$$$ 之间的整数(含)。每条边都有不同的权重。
- 该图的形成方式使得有一种方法可以为满足以下条件的键树中的每条边 $$$i$$$ 分配权重 $$$W_i$$$:对于每对边 $$$(i, j)$$$,如果 $$$i<j$$$,则 $$$W_i<W_j$$$。 对于每对不同的顶点索引 $$$(x, y)$$$,键树中从顶点 $$$x$$$ 到 $$$y$$$ 的唯一简单路径的成本等于图中经过顶点 $$$x$$$ 和 $$$y$$$ 的简单电路的最小成本。
- 请注意,图允许有多边,但不允许有自环。

打印以 $$$998\,244\,353$$$ 为模的答案。

当且仅当存在三元组 $$$(a, b, c)$$$ 且一个图中存在一条边连接顶点 $$$a$$$ 和 $$$b$$$ 且权重为 $$$c$$$ 的边,但另一个图中不存在,则两个图被视为不同。

输入

第一行包含一个整数 $$$N$$$ ($$$2 \le N \le 10^5$$$) — 键树中的顶点数。

接下来的 $$$N-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$U_i$$$ 和 $$$V_i$$$ ($$$1 \le U_i, V_i \le N$$$) — 连接顶点 $$$U_i$$$ 和 $$$V_i$$$ 的边。输入中的图是一棵树。

输出

一个整数,表示满足问题条件模 $$$998\,244\,353$$$ 的不同无向加权图的数量。

示例

输入 #1

4
3 2
1 3
4 3

输出 #1

540

注意

下面是满足的图表示例。

以下是与上图对应的键树中边权重的分配。

作为示例,考虑一对顶点索引 $$$(1, 4)$$$。

- 图中这对顶点的电路为 $$$3 \xrightarrow{2} 2 \xrightarrow{4} 4 \xrightarrow{6} 2 \xrightarrow{1} 1 \xrightarrow{5} 3$$$,成本为 $$$6$$$。
- 这对顶点在键树中的路径为 $$$1 \xrightarrow{5} 3 \xrightarrow{6} 4$$$,成本为 $$$6$$$。