F - Logical Operations on Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 800 点

問題文

1 から N の番号がついた N 頂点の木が与えられます。

i 番目の辺は頂点 a_i と b_i をつないでいます。

すぬけ君は頂点には 0 か 1 のラベルを、辺には AND か OR のラベルをつけることにしました。 頂点と辺へのラベルのつけ方は 2^{2N-1} 通りあります。それらのうち下記の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

条件：操作 を N-1 回行ったのち、残った頂点についているラベルが 1 になるような操作手順が存在する。操作は下記の手順からなる。

  • 辺を 1 本選んで縮約する(消された 2 個の頂点に書かれていたラベルを x,y、消された辺に書かれていたラベルを \mathrm{op} とする)。
  • \mathrm{op} が AND ならば \mathrm{AND}(x,y) を、OR ならば \mathrm{OR}(x,y) を新たな頂点にラベルとしてつける。

注記

  • 演算 \mathrm{AND} の定義は次の通りです：\mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1
  • 演算 \mathrm{OR} の定義は次の通りです：\mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0
  • 頂点 s と頂点 t を結ぶ辺を縮約する際は、その辺を取り除くと同時に 2 頂点を併合します。縮約後の木において、併合により生まれた頂点と頂点 u を結ぶ辺が存在するのは、縮約前の木において s と u を結ぶ辺または t と u を結ぶ辺が存在するときであり、またそのときに限られます。

制約

  • 与えられる入力は全て整数
  • 2 \leq N \leq 10^{5}
  • 1 \leq a_i, b_i \leq N
  • 与えられるグラフは木

入力

入力は以下の形式で標準入力から与えられる。

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

出力

問題文中の条件を満たすラベルのつけ方の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

2
1 2

出力例 1

4

入力例 2

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

出力例 2

283374562
  • 998244353 で割ったあまりを出力するのを忘れずに。

Score : 800 points

Problem Statement

Given is a tree with N vertices numbered 1 through N.

The i-th edge connects Vertices a_i and b_i.

Snuke will label each vertex with 0 or 1 and each edge with AND or OR. Among the 2^{2N-1} ways to label the vertices and edges, find the number of ways that satisfy the following condition, modulo 998244353.

Condition: There exists a sequence of N-1 operations ending up with one vertex labeled 1, where each operation consists of the steps below.

  • Choose one edge and contract it. Here, let x and y be the labels of the erased vertices and \mathrm{op} be the label of the erased edge.
  • If \mathrm{op} is AND, label the new vertex with \mathrm{AND}(x,y); if \mathrm{op} is OR, label the new vertex with \mathrm{OR}(x,y).

Notes

  • The operation \mathrm{AND} is defined as follows: \mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1.
  • The operation \mathrm{OR} is defined as follows: \mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0.
  • When contracting the edge connecting Vertex s and Vertex t, we merge the two vertices while removing that edge. After the contraction, there is an edge connecting the new vertex and vertex u if and only if there was an edge connecting s and u or connecting t and u before the contraction.

Constraints

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

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 number of ways to label the tree that satisfy the condition in Problem Statement, modulo 998244353.

Sample Input 1

2
1 2

Sample Output 1

4

Sample Input 2

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

Sample Output 2

283374562
  • Remember to print the count modulo 998244353.