F - Tree Vertices XOR 解説 /

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

配点 : 2000 点

問題文

N 頂点の木が与えられます。 木の頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 u_i, v_i を結びます。

はじめ、木の各頂点には 1 という数が書かれています。

1 回の操作で、あなたは以下を行えます。

  • 木から頂点 v を選ぶ。v に隣接する頂点全てに書き込まれた値の XOR が X であるとする。v に書かれた値が a_v であるとして、この値を (a_v\ \mathrm{XOR}\ X) に置き換える。

この操作を任意の有限回（0 回も含む）行えるとして、得られる木の形態は何通りあるでしょうか。この数は大きい可能性があるため、これを 998244353 で割った余りを出力してください。

ここで、木の 2 つの形態は、書かれた数が異なるような頂点 v が存在するときに異なるとみなされます。

制約

  • 3 \le N \le 2\cdot 10^5
  • 1\le u_i, v_i \le N
  • u_i \neq v_i
  • 入力が表すグラフは木である。

入力

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

初期状態から得られる木の形態の個数を 998244353 で割った余りを出力せよ。

入力例 1

4
1 2
2 3
3 4

出力例 1

10

頂点 1,2,3,4 に a,b,c,d が書かれている形態を abcd と表すと、到達可能な形態は 1111, 1110, 1100, 1000, 0111, 0110, 0100, 0011, 0010, 0001 です。

入力例 2

5
1 2
1 3
1 4
1 5

出力例 2

24

入力例 3

6
1 3
2 3
3 4
4 5
4 6

出力例 3

40

入力例 4

9
1 2
2 3
1 4
4 5
1 6
6 7
7 8
8 9

出力例 4

255

Score : 2000 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered from 1 to N, and the i-th edge connects vertices u_i and v_i.

Initially, on each vertex of the tree is written number 1.

In one operation, you can do the following:

  • Choose any vertex v of the tree. Let X be the XOR of the values written in the neighbors of v. Then, if the number written on v is a_v, replace it by (a_v\ \mathrm{XOR}\ X).

You can perform this operation any finite (maybe zero) number of times. How many configurations can you achieve? As this number can be large, output it modulo 998244353.

Two configurations are called different if there exists a vertex v, such that the numbers written in v in these configurations are different.

Constraints

  • 3 \le N \le 2\cdot 10^5
  • 1\le u_i, v_i \le N
  • u_i \neq v_i
  • The input represents a valid tree.

Input

Input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the number of configurations you can get from the initial state, modulo 998244353.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

10

We can get the following configurations (abcd means vertices 1,2,3,4 have a,b,c,d written on them): 1111, 1110, 1100, 1000, 0111, 0110, 0100, 0011, 0010, 0001.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

24

Sample Input 3

6
1 3
2 3
3 4
4 5
4 6

Sample Output 3

40

Sample Input 4

9
1 2
2 3
1 4
4 5
1 6
6 7
7 8
8 9

Sample Output 4

255