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$。

题目描述

Vasya has a tree with $ n $ vertices numbered from $ 1 $ to $ n $ , and $ n - 1 $ edges numbered from $ 1 $ to $ n - 1 $ . Initially each vertex contains a token with the number of the vertex written on it. Vasya plays a game. He considers all edges of the tree by increasing of their indices. For every edge he acts as follows: - If both endpoints of the edge contain a token, remove a token from one of the endpoints and write down its number. - Otherwise, do nothing. The result of the game is the sequence of numbers Vasya has written down. Note that there may be many possible resulting sequences depending on the choice of endpoints when tokens are removed. Vasya has played for such a long time that he thinks he exhausted all possible resulting sequences he can obtain. He wants you to verify him by computing the number of distinct sequences modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the number of vertices of the tree. The next $ n - 1 $ lines describe edges of the tree. The $ i $ -th of these lines contains two integers $ u_i, v_i $ ( $ 1 \leq u_i, v_i \leq n $ ) — endpoints of the edge with index $ i $ . It is guaranteed that the given graph is indeed a tree.

输出格式

Print a single integer — the number of distinct sequences modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

5
1 2
1 3
1 4
1 5

输出样例 #1

5

输入样例 #2

7
7 2
7 6
1 2
7 5
4 7
3 5

输出样例 #2

10

说明

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