AT_arc121_f [ARC121F] Logical Operations on Tree

[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

N/A

### 注記 - 演算 $ \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 $ で割ったあまりを出力するのを忘れずに。