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) $ .