『MdOI R2』Resurrection

如果你不清楚本题的某些定义，可以阅读【说明/提示】部分。

有一棵包含 $n$ 个节点的树 $T$，它的所有边依次编号为 $1$ 至 $n-1$。 保证对于 $T$ 中任意一个节点 $u$ ，从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点。 按照如下步骤生成一张包含 $n$ 个节点的无向图 $G$： 选取一个 $1 \sim n-1$ 的排列 $p$，然后依次进行 $n-1$ 次操作。在进行第 $i$ 次操作时，首先删除树 $T$ 中编号为 $p_i$ 的边 $(a,b)$，然后，记 $u$ 和 $v$ 分别为当前树 $T$ 中与 $a,b$ 联通的所有点中，编号最大的点，并在图 $G$ 的 $u$ 号点和 $v$ 号点之间连一条边。 求对于给定的树 $T$，按上述方式一共可以生成多少种本质不同的图 $G$。图 $G_1$ 和 $G_2$ 本质不同当且仅当存在 $u$ 和 $v$ 满足在 $G_1$ 中不存在边 $(u,v)$，而 $G_2$ 中存在。 因为答案可能很大，你只需要求出答案对 $998244353$ 取模的值。

第一行一个整数 $n$，表示树 $T$ 中的节点数量。 接下来 $n-1$ 行，第 $i$ 行两个整数 $u,v$，表示在 $T$ 中编号为 $i$ 的边是 $(u,v)$。

一行一个整数，答案对 $998244353$ 取模的值。

4
1 4
2 3
3 4

2

11
1 4
2 6
3 11
4 6
5 6
6 7
7 9
8 9
9 10
10 11

4605

【帮助与提示】 为方便选手测试代码，本题额外提供一组附加样例供选手使用。 [样例输入](https://www.luogu.com.cn/paste/09anxo5k) [样例输出](https://www.luogu.com.cn/paste/3idipkty) --- 【样例解释】 样例一中可能生成的图 $G$ 如图所示：  当 $p = \{1,2,3\},\{2,1,3\},\{2,3,1\}$ 时将生成右侧的图，否则将生成左侧的图。 对于样例二，我有一个绝妙的解释，只可惜这里空白的位置太小，写不下。 --- 【数据范围】 **本题采用捆绑测试。** 对于全部数据，保证 $1 \leq n \leq 3 \times 10^3$，$1 \leq u,v \leq n$。 保证，输入的边形成一棵树，且对于任意一个节点 $u$ ，从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点。 | 子任务编号 | $n\leq$ | 特殊性质 | 分值 | | :--------: | :-----: | :-----------------------: | :--: | | Subtask 1 | $5$ | 无 | $32$ | | Subtask 2 | $14$ | 无 | $16$ | | Subtask 3 | $10^3$ | 所有节点都与 $n$ 号点直接相连 | $1$ | | Subtask 4 | $10^3$ | 树的形态是一条链 | $7$ | | Subtask 5 | $50$ | 无 | $22$ | | Subtask 6 | $3 \times 10^3$ | 无 | $22$ | --- 下面是本题用到的一些定义： - 一棵树是一张有 $n$ 个节点，$n-1$ 条边的无向连通图。 - 边 $(u,v)$ 表示连接点 $u$ 和点 $v$ 的一条边。 - 一条路径是一个序列 $p_1,p_2 \ldots p_k$ ，满足对于任意 $1 \leq i < k$，边 $(p_i,p_{i+1})$ 都存在于 $T$ 中，且 **没有被之前的操作删除**。 - 点 $u$ 和 $v$ 联通当且仅当存在一条路径 $p_1,p_2 \ldots p_k$ 满足 $p_1=u$ 且 $p_k=v$。任何一个点都和自己联通。