AT_ndpc2026_t 独立集合

頂点に $ 1 $ から $ N $ の番号が付いた $ N $ 頂点の木が与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ辺です。 頂点の集合 $ S $ が次の条件を満たす時、 $ S $ を **独立集合** と呼びます。 - $ S $ に含まれる任意の異なる $ 2 $ 頂点 $ u, v $ について、 $ u $ と $ v $ は木の上で隣接していない。 頂点 $ v $ について、 $ v \in S $ を満たす独立集合全てからなる集合を $ F_v $ と表します。 $ Q $ 個のクエリを処理してください。クエリでは $ 1 \leq v \leq N $ を満たす整数 $ v $ および整数 $ q $ が与えられるので、 $ \displaystyle \left( \sum_{S \in F_v} q^{|S|}\right) \bmod 998244353 $ を計算してください。ここで $ |S| $ は集合のサイズを意味します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ v $ $ q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - 全てのクエリにおいて $ v=1 $ が成り立つデータセットに正解した場合、 $ 5 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ 番目のクエリについて考えます。頂点 $ 1 $ を含む独立集合は $ \lbrace 1 \rbrace $ と $ \lbrace 1, 4 \rbrace $ の $ 2 $ 個です。よって $ 1^1 + 1^2 = 2 $ を出力します。 ### Constraints - $ 2 \leq N \leq 1.3 \times 10^5 $ - $ 1 \leq Q \leq 1.3 \times 10^5 $ - $ 1 \leq u_i \lt v_i \leq N $ - 入力で与えられるグラフは木 - $ 1 \leq v \leq N $ - $ 1 \leq q \lt 998244353 $ - 入力される値は全て整数