AT_ndpc2026_t 独立集合

You are given a tree with $ N $ vertices, numbered from $ 1 $ to $ N $ . The $ i $ -th edge connects vertices $ u_i $ and $ v_i $ . A set of vertices $ S $ is called an **independent set** if it satisfies the following condition: - For any two distinct vertices $ u, v \in S $ , $ u $ and $ v $ are not adjacent in the tree. For a vertex $ v $ , let $ F_v $ be the set of all independent sets $ S $ such that $ v \in S $ . You are given $ Q $ queries. In each query, you are given an integer $ v $ ( $ 1 \leq v \leq N $ ) and an integer $ q $ . Compute: $ \displaystyle \left( \sum_{S \in F_v} q^{|S|}\right) \bmod 998244353 $ Here, $ |S| $ denotes the size of the set $ S $ .

The input is given from standard input in the following format: > $ 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 $ Each query is given in the following format: > $ v $ $ q $

Print $ Q $ lines. On the $ i $ -th line, output the answer to the $ i $ -th query.

### Partial Score This problem has partial scoring. - If all queries satisfy $ v=1 $ , you will get $ 5 $ points. ### Sample Explanation 1 Consider the first query. The independent sets that contain vertex $ 1 $ are $ {1} $ and $ {1, 4} $ , so there are $ 2 $ such sets. Therefore, output $ 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 < v_i \leq N $ - The given graph is a tree - $ 1 \leq v \leq N $ - $ 1 \leq q < 998244353 $ - All input values are integers