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$ 的结果。

说明/提示

In the first sample case the distinct sequences are $ (1), (2, 1), (2, 3, 1), (2, 3, 4, 1), (2, 3, 4, 5) $ . Int the second sample case the distinct sequences are $ (2, 6, 5, 3), (2, 6, 5, 7), (2, 6, 7, 2), (2, 6, 7, 5), (2, 7, 3), (2, 7, 5), (7, 1, 3), (7, 1, 5), (7, 2, 3), (7, 2, 5) $ .