P6383 ‘MdOI R2’ Resurrection

If you are not clear about some definitions in this problem, you can read the [Notes / Hint] section.

There is a tree $T$ with $n$ nodes, and all its edges are numbered from $1$ to $n-1$ in order. It is guaranteed that for any node $u$ in $T$, the simple path from $u$ to node $n$ does not pass through any node whose index is less than $u$. Generate an undirected graph $G$ with $n$ nodes by the following steps: Choose a permutation $p$ of $1 \sim n-1$, and then perform $n-1$ operations in order. In the $i$-th operation, first delete the edge $(a,b)$ in tree $T$ whose index is $p_i$. Then let $u$ and $v$ be, respectively, the node with the largest index among all nodes currently connected to $a$ and to $b$ in the current tree $T$. Add an edge between node $u$ and node $v$ in graph $G$. For the given tree $T$, find how many essentially different graphs $G$ can be generated in total by the method above. Graphs $G_1$ and $G_2$ are essentially different if and only if there exist $u$ and $v$ such that edge $(u,v)$ does not exist in $G_1$, but exists in $G_2$. Since the answer may be very large, you only need to output it modulo $998244353$.

The first line contains one integer $n$, the number of nodes in tree $T$. The next $n-1$ lines each contain two integers $u, v$. In the $i$-th line, it means the edge in $T$ with index $i$ is $(u,v)$.

Output one integer: the answer modulo $998244353$.

【Help and Hint】 To make it easier for contestants to test their code, this problem additionally provides an extra sample for contestants to use. [Sample Input](https://www.luogu.com.cn/paste/09anxo5k) [Sample Output](https://www.luogu.com.cn/paste/3idipkty) --- 【Sample Explanation】 In sample 1, the possible graphs $G$ that can be generated are shown in the figure:  When $p = \{1,2,3\},\{2,1,3\},\{2,3,1\}$, the graph on the right will be generated; otherwise, the graph on the left will be generated. For sample 2, I have a wonderful explanation, but unfortunately this blank space is too small to write it down. --- 【Constraints】 **This problem uses bundled tests.** For all testdata, it is guaranteed that $1 \leq n \leq 3 \times 10^3$, $1 \leq u,v \leq n$. It is guaranteed that the input edges form a tree, and for any node $u$, the simple path from $u$ to node $n$ does not pass through any node whose index is less than $u$. | Subtask ID | $n\leq$ | Special Property | Score | | :--------: | :-----: | :--------------: | :---: | | Subtask 1 | $5$ | None | $32$ | | Subtask 2 | $14$ | None | $16$ | | Subtask 3 | $10^3$ | All nodes are directly connected to node $n$ | $1$ | | Subtask 4 | $10^3$ | The tree is a chain | $7$ | | Subtask 5 | $50$ | None | $22$ | | Subtask 6 | $3 \times 10^3$ | None | $22$ | --- Below are some definitions used in this problem: - A tree is an undirected connected graph with $n$ nodes and $n-1$ edges. - Edge $(u,v)$ means an edge connecting node $u$ and node $v$. - A path is a sequence $p_1,p_2 \ldots p_k$ such that for any $1 \leq i < k$, edge $(p_i,p_{i+1})$ exists in $T$, and **has not been deleted by previous operations**. - Nodes $u$ and $v$ are connected if and only if there exists a path $p_1,p_2 \ldots p_k$ such that $p_1=u$ and $p_k=v$. Every node is connected to itself. Translated by ChatGPT 5