CF1276D Tree Elimination

题目描述

给定一棵 $n$ 个点的树,点编号 $1 \sim n$,第 $i$ 条边连接 $a_i$ 和 $b_i$。 初始时你有一个空的序列,树上的 $n$ 个点都有标记。 现在按照边的编号从小到大考虑每一条边: - 如果这一条边连接的两个点都有标记,则选择其中的一个点,擦除它的标记并将它的编号放入序列的末端; - 否则什么都不做。 求能够由上述操作得到的不同的序列数量 $\bmod\ 998244353$ 的结果。

输入格式

第一行一个正整数 $n$($2 \leq n \leq 2 \times 10^5$)表示树的点数,接下来 $n-1$ 行每行两个正整数表示第 $i$ 条边连接的两个点。

输出格式

一行一个整数表示序列数量 $\bmod\ 998244353$ 的结果。

说明/提示

在第一个样例中,不同的序列为 $(1)$, $(2, 1)$, $(2, 3, 1)$, $(2, 3, 4, 1)$, $(2, 3, 4, 5)$。 在第二个样例中,不同的序列为 $(2, 6, 5, 4)$,$(2, 6, 5, 7)$,$(2, 6, 7, 3)$,$(2, 6, 7, 5)$,$(2, 7, 3)$,$(2, 7, 5)$,$(7, 1, 3)$,$(7, 1, 5)$,$(7, 2, 3)$,$(7, 2, 5)$。