F-小红删树_牛客周赛 Round 133

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一棵包含 $n$ 个节点的树，小红将进行如下操作：
$\hspace{23pt}\bullet$ 考虑当前森林的所有连通块，对于每个连通块，独立地、均匀随机地选择该连通块中的一个节点，之后删除所有被选中的节点（删除后其相邻边也会被移除）。
$\hspace{15pt}$ 若某一轮操作开始前所有节点已被删除，则该轮及后续操作无法执行。

$\hspace{15pt}$ 请你计算：在前 $2$ 次操作结束后仍有节点剩余，且在第 $3$ 次操作结束后节点全部被删除的概率。可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \times q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998\,244\,353$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。

【名词解释】
$\hspace{15pt}$ 连通块：也称连通分量，满足，
$\hspace{23pt}\bullet\,$ 是原图的一个子图；
$\hspace{23pt}\bullet\,$ 连通块内的任意两个顶点之间都存在路径相连，且路径上的点也在连通块内；
$\hspace{23pt}\bullet\,$ 是极大的，即不能再通过添加原图中的其他顶点而依旧保持连通性；
$\hspace{15pt}$ 单独的点也构成一个连通块。

输入描述:

第一行输入一个整数  ，表示树的节点数。
接下来  行，第  行输入两个整数 ，表示树中第  条边连接节点  和节点 。保证输入构成一棵树。

输出描述:

输出一行一个整数，代表答案对  取模的结果。

示例1

输入

复制

3
1 2
2 3

输出

复制

665496236

说明

只有当第一次删除选择了  号点时不符合题意，此时一定会在第二次删除时删除所有节点。所以答案为 。
我们能够找到，，对  取模后恰好等于分子 ，所以  是需要输出的答案。

示例2

输入

复制

输出

复制

748683265

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。