AT_dwacon6th_final_c Tree Shrinking
题目描述
给定一棵包含 $N$ 个顶点的树，顶点依次编号为 $1$ 到 $N$。这棵树包含 $N-1$ 条边，每条边标号为 $1$ 到 $N-1$，其中第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。
尼万戈君将执行 $N-1$ 次操作。具体操作步骤如下：
1. 随机等概率选择一条边（记为 $e$，其端点为 $u$ 和 $v$）。
2. 在这次操作中，$u$ 的度数为 $x$，$v$ 的度数为 $y$，那么这次操作将获得 $xy$ 分。
3. 移除边 $e$，并将顶点 $u$ 和 $v$ 合并成一个顶点，即对边进行收缩。
经过 $N-1$ 次操作后，计算尼万戈君获得的总分的期望值，并将该期望值乘以 $(N-1)!$（一个可以被证明为整数的值），最后求此结果除以 $998244353$ 的余数。
输入格式
通过标准输入提供数据，格式如下：
> $ N $
> $ a_1 $ $ b_1 $
> $\vdots$
> $ a_{N-1} $ $ b_{N-1} $
输出格式
输出最终的答案。
说明/提示
- $2 \leq N \leq 10^5$
- $1 \leq a_i, b_i \leq N$
- 输入的图结构为一棵树
### 示例解释
- 比如，在第一次操作中，如果选择了边 $1$，则此次操作得分为 $9$，树的结构会发生变化，如下图所示：
- 请计算最后结果对 $998244353$ 取模后的值。
**本翻译由 AI 自动生成**