No.2047 Path Factory
タグ : / 解いたユーザー数 56
作問者 : 👑
hitonanode
sapphire__15
Problem Statement
You are given a tree with $N$ vertices. The $i$-th edge connects vertex $u_i$ and vertex $v_i$.
There are $2^{N-1}$ ways to delete $0$ or more edges. Among them, how many result in every connected component being a path graph?
Since the answer can be very large, find it modulo $998244353$.
Here, a path graph is a tree that has exactly $2$ vertices of degree $1$ and in which all other vertices have degree $2$. Note that a graph with $1$ vertex is not considered a path graph.
Constraints
- $2\le N\le 10^5$
- $1\le u_i,v_i\le N$
- The given graph is a tree.
- All input values are integers.
Input
$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
Output
Output the answer modulo $998244353$.
Sample
Sample 1
Input
6 1 2 2 3 3 4 4 5 5 6
Output
5
The $5$ ways are shown in the figure below.
Sample 2
Input
4 1 2 2 3 2 4
Output
0
No way satisfies the condition.
Sample 3
Input
12 1 3 3 5 5 7 7 9 9 11 12 10 10 8 8 6 6 4 4 2 6 7
Output
41
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。