← 返回题目列表

Codeforces · 1762/E

E. 树总和

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

如果每条边的权重是 $$$1$$$ 或 $$$-1$$$,并且对于每个顶点 $$$i$$$,以 $$$i$$$ 作为一个端点的所有边的边权重的乘积为$$$-1$$$。

给你一个正整数$$$n$$$。有 $$$n^{n-2} \cdot 2^{n-1}$$$ 不同的$$$^\dagger$$$ 边加权树,其 $$$n$$$ 顶点编号从 $$$1$$$ 到 $$$n$$$,这样每条边要么是 $$$1$$$ 要么是 $$$-1$$$。你的任务是找到所有这样的好树的 $$$d(1,n)^\ddagger$$$ 的总和。由于答案可能相当大,因此您只需对 $$$998\,244\,353$$$ 求模即可。

$$$^\dagger$$$ 如果出现以下任一情况,则认为两棵树是不同的:

- 存在两个顶点,其中一棵树中它们之间有一条边,而另一棵树中则没有边。
- 存在两个顶点,两棵树中它们之间都有一条边,但一棵树中它们之间的边的权重与另一棵树中的不同。

请注意,根据凯莱公式,$$$n$$$ 标记顶点上的树数量为 $$$n^{n-2}$$$。由于我们有 $$$n-1$$$ 边,因此存在 $$$2^{n-1}$$$ 可能的权重分配(权重可以是 $$$1$$$ 或 $$$-1$$$)。这就是为什么不同边加权树的总数为 $$$n^{n-2} \cdot 2^{n-1}$$$。

$$$^\ddagger$$$ $$$d(u,v)$$$ 表示从 $$$u$$$ 到 $$$v$$$ 的唯一简单路径上所有边的权重之和。

输入

输入的第一行也是唯一一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$)。

输出

唯一的输出行应包含一个整数,即所需的答案,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

2

输出 #1

998244352

输入 #2

1

输出 #2

0

输入 #3

4

输出 #3

998244343

输入#4

10

输出#4

948359297

输入 #5

43434

输出 #5

86232114

注意

在第一个测试用例中,只有 $$$1$$$ 不同的好树。该树的 $$$d(1,2)$$$ 值为 $$$-1$$$,模 $$$998\,244\,353$$$ 后为 $$$998\,244\,352$$$。

在第二个测试用例中,任何树的 $$$d(1,1)$$$ 的值为 $$$0$$$,因此答案为 $$$0$$$。

在第三个测试用例中,有 $$$16$$$ 不同的好树。 $$$d(1,4)$$$ 的值为:

- $$$-2$$$ 为 $$$2$$$ 树;
- $$$-1$$$ 为 $$$8$$$ 树;
- $$$0$$$ 为 $$$4$$$ 树;
- $$$1$$$ 为 $$$2$$$ 树。

所有树的 $$$d(1,4)$$$ 之和为 $$$2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10$$$,模数下为 $$$998\,244\,343$$$ $$$998\,244\,353$$$。