CF1762E Tree Sum

我们称一个有 $n$ 个顶点（编号为 $1$ 到 $n$）的带权树是“好”的，如果每条边的权值要么是 $1$，要么是 $-1$，并且对于每个顶点 $i$，所有以 $i$ 为端点的边的权值的乘积为 $-1$。 给定一个正整数 $n$。共有 $n^{n-2} \cdot 2^{n-1}$ 种不同的带权树，树的顶点编号为 $1$ 到 $n$，每条边的权值为 $1$ 或 $-1$。你的任务是求所有“好”的树中 $d(1, n)$ 的和。由于答案可能很大，只需输出其对 $998\,244\,353$ 取模的结果。 $^\dagger$ 如果满足以下任一条件，则认为两棵树是不同的： - 存在两个顶点，在一棵树中它们之间有边，而在另一棵树中没有。 - 存在两个顶点，在两棵树中它们之间都有边，但这条边的权值不同。 注意，根据 [Cayley 公式](https://rb.gy/hho7vu)，$n$ 个有标号顶点的树的数量为 $n^{n-2}$。由于有 $n-1$ 条边，每条边有 $2$ 种权值分配方式（$1$ 或 $-1$），因此不同的带权树总数为 $n^{n-2} \cdot 2^{n-1}$。 $^\ddagger$ $d(u, v)$ 表示从 $u$ 到 $v$ 的唯一简单路径上所有边权值的和。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）。

输出一个整数，表示所有“好”的树中 $d(1, n)$ 的和，对 $998\,244\,353$ 取模。

在第一个测试用例中，只有 $1$ 棵不同的“好”树。该树的 $d(1,2)$ 为 $-1$，模 $998\,244\,353$ 后为 $998\,244\,352$。 在第二个测试用例中，任意树的 $d(1,1)$ 都为 $0$，所以答案为 $0$。 在第三个测试用例中，共有 $16$ 棵不同的“好”树。$d(1,4)$ 的取值如下： - $2$ 棵树为 $-2$； - $8$ 棵树为 $-1$； - $4$ 棵树为 $0$； - $2$ 棵树为 $1$。 所有树的 $d(1,4)$ 之和为 $2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10$，模 $998\,244\,353$ 后为 $998\,244\,343$。 由 ChatGPT 4.1 翻译