201423: [AtCoder]ARC142 D - Deterministic Placing

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $800$ points

Problem Statement

We have a tree with $N$ vertices, numbered $1, \ldots, N$. For each $i=1,\ldots,N-1$, the $i$-th edge connects Vertex $a_i$ and Vertex $b_i$.
An operation on this tree when at most one piece is put on each vertex is defined as follows.

  • Simultaneously move every piece to one of the vertices adjacent to the one occupied by the piece.

An operation is said to be good when the conditions below are satisfied.

  • Each edge is traversed by at most one piece.
  • Each vertex will be occupied by at most one piece after the operation.

Takahashi will put a piece on one or more vertices of his choice. Among the $2^N-1$ ways to put pieces, find the number of ones that satisfy the condition below, modulo $998244353$.

  • For every non-negative integer $K$, the following holds.
    • It is possible to perform a good operation $K$ times.
    • Let $S_K$ be the set of vertices occupied by pieces just after $K$ good operations. Then, $S_K$ is unique.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq a_i \lt b_i \leq N$
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

Output

Print the answer.


Sample Input 1

3
1 2
1 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

  • Put a piece on Vertex $1$ and Vertex $2$.
  • Put a piece on Vertex $1$ and Vertex $3$.

Note that he must put a piece on at least one vertex.


Sample Input 2

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

Sample Output 2

0

There might be no way to satisfy the condition.


Sample Input 3

19
9 14
2 13
1 3
17 19
13 18
12 19
4 5
2 10
4 9
8 11
3 15
6 8
8 10
6 19
9 13
11 15
7 17
16 17

Sample Output 3

100

Input

题意翻译

给定一棵 $N$ 个点的树。初始时可以在某些节点上放置一颗棋子,且放置的棋子总数至少为 $1$,则共有 $2^N -1$ 种放置方案。 定义一次操作为, - 对于每颗棋子,将其沿着树边移动到与当前节点相邻的一个节点上。 在一次操作内,所有棋子的移动是同时进行的,并且需要遵循以下规则。 - 每条树边最多被一颗棋子经过。 - 移动后每个节点上至多有一颗棋子。 现在你需要统计 $2^N-1$ 种放置方案中,满足以下条件的方案数,对 $998244353$ 取模。 - 对于每个非负整数 $K$,满足以下条件。 - 至少能进行 $K$ 次操作。 - 无论如何进行这 $K$ 次操作,最终所有棋子占据的节点集合唯一。 $2 \le N \le 2 \times 10^5$ 。

加入题单

上一题 下一题 算法标签: