CF1762E.Tree Sum

Let us call an edge-weighted tree with $n$ vertices numbered from $1$ to $n$ good if the weight of each edge is either $1$ or $-1$ and for each vertex $i$, the product of the edge weights of all edges having $i$ as one endpoint is $-1$.

You are given a positive integer $n$. There are $n^{n-2} \cdot 2^{n-1}$ distinct$^\dagger$ edge-weighted trees with $n$ vertices numbered from $1$ to $n$ such that each edge is either $1$ or $-1$. Your task is to find the sum of $d(1,n)^\ddagger$ of all such trees that are good. Since the answer can be quite large, you only need to find it modulo $998\,244\,353$.

$^\dagger$ Two trees are considered to be distinct if either:

• there exists two vertices such that there is an edge between them in one of the trees, and not in the other.
• there exists two vertices such that there is an edge between them in both trees but the weight of the edge between them in one tree is different from the one in the other tree.

Note that by Cayley's formula, the number of trees on $n$ labeled vertices is $n^{n-2}$. Since we have $n-1$ edges, there are $2^{n-1}$ possible assignment of weights(weight can either be $1$ or $-1$). That is why total number of distinct edge-weighted tree is $n^{n-2} \cdot 2^{n-1}$.

$^\ddagger$ $d(u,v)$ denotes the sum of the weight of all edges on the unique simple path from $u$ to $v$.

我们称一棵具有 $n$ 个顶点（编号为 $1$ 到 $n$）且每条边带权的树为好树，若其每条边的权值均为 $1$ 或 $-1$，且对每个顶点 $i$，所有以 $i$ 为一个端点的边的权值之积为 $-1$。

给定一个正整数 $n$。在所有顶点编号为 $1$ 到 $n$ 的边带权树中，满足每条边权值为 $1$ 或 $-1$ 的不同$^\dagger$ 树共有 $n^{n-2} \cdot 2^{n-1}$ 棵。你的任务是：对所有这样的好树，求其 $d(1,n)^\ddagger$ 的总和。由于答案可能非常大，你只需输出该总和对 $998\,244\,353$ 取模的结果。

$^\dagger$ 两棵树被视为不同，当且仅当满足以下任一条件：

• 存在两个顶点，在其中一棵树中它们之间有边相连，而在另一棵树中没有；
• 存在两个顶点，在两棵树中它们之间均有边相连，但这两条边的权值不同。

注意，根据 Cayley 公式，$n$ 个带标号顶点的树的总数为 $n^{n-2}$。由于每棵树恰有 $n-1$ 条边，而每条边可独立地赋予权值 $1$ 或 $-1$，故权值分配方式共 $2^{n-1}$ 种。因此，不同的边带权树总数为 $n^{n-2} \cdot 2^{n-1}$。

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

The first and only line of input contains a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$).

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

The only line of output should contain a single integer, the required answer, modulo $998\,244\,353$.

输出仅包含一行，其中为一个整数，即所求答案对 $998\,244\,353$ 取模的结果。

In the first test case, there is only $1$ distinct good tree. The value of $d(1,2)$ for that tree is $-1$, which is $998\,244\,352$ under modulo $998\,244\,353$.

In the second test case, the value of $d(1,1)$ for any tree is $0$, so the answer is $0$.

In the third test case, there are $16$ distinct good trees. The value of $d(1,4)$ is:

• $-2$ for $2$ trees;
• $-1$ for $8$ trees;
• $0$ for $4$ trees;
• $1$ for $2$ trees.

The sum of $d(1,4)$ over all trees is $2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10$, which is $998\,244\,343$ under modulo $998\,244\,353$.

在第一个测试用例中，仅有 $1$ 棵不同的好树。该树的 $d(1,2)$ 值为 $-1$，在模 $998\,244\,353$ 意义下等于 $998\,244\,352$。

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

在第三个测试用例中，共有 $16$ 棵不同的好树。其中 $d(1,4)$ 的值满足：

• 对于 $2$ 棵树，$d(1,4) = -2$；
• 对于 $8$ 棵树，$d(1,4) = -1$；
• 对于 $4$ 棵树，$d(1,4) = 0$；
• 对于 $2$ 棵树，$d(1,4) = 1$。

所有树的 $d(1,4)$ 值之和为 $2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10$，在模 $998\,244\,353$ 意义下等于 $998\,244\,343$。