[ARC121F] Logical Operations on Tree

给定一棵树，给每个点填 $0$ 或 $1$，给每条边填 $\text{AND}$ 或 $\text{OR}$，在所有 $2^{n+n-1}$ 种填法中，计数有多少种满足存在一种缩边的顺序，使得每次把一条边的两个端点缩成一个点，权为原端点与边的运算值，最终点的权为 $1$。

[problemUrl]: https://atcoder.jp/contests/arc121/tasks/arc121_f $ 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) $ を新たな頂点にラベルとしてつける。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $

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

2
1 2

4

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

283374562

### 注記 - 演算 $ \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 $ - 与えられるグラフは木 ### Sample Explanation 2 \- $ 998244353 $ で割ったあまりを出力するのを忘れずに。