T - Independent Set Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MiB

配点 : 10 点

問題文

頂点に 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| は集合のサイズを意味します。

制約

  • 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
  • 入力される値は全て整数

部分点

この問題には部分点が設定されている。

  • 全てのクエリにおいて v=1 が成り立つデータセットに正解した場合、5 点が与えられる。

入力

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

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 番目のクエリへの答えを出力せよ。

入力例 1

4 2
1 2
1 3
2 4
1 1
2 3

出力例 1

2
12

1 番目のクエリについて考えます。頂点 1 を含む独立集合は \lbrace 1 \rbrace と \lbrace 1, 4 \rbrace の 2 個です。よって 1^1 + 1^2 = 2 を出力します。

入力例 2

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

出力例 2

16
162
768
2500
6480
14406
28672
52488
90000
146410

入力例 3

10 10
1 2
1 3
2 4
4 5
4 6
2 7
5 8
8 9
6 10
5 844033520
8 780395612
2 285523486
6 13801767
3 487663185
3 667406485
7 672229269
7 207478896
5 769551740
7 806405364

出力例 3

665599367
675643489
193550820
987507475
230555342
555586355
204648376
83113599
299301383
545057926

Score : 10 points

Problem Statement

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.

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

Partial Score

This problem has partial scoring.

  • If all queries satisfy v=1, you will get 5 points.

Input

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

Output

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

Sample Input 1

4 2
1 2
1 3
2 4
1 1
2 3

Sample Output 1

2
12

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.

Sample Input 2

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

Sample Output 2

16
162
768
2500
6480
14406
28672
52488
90000
146410

Sample Input 3

10 10
1 2
1 3
2 4
4 5
4 6
2 7
5 8
8 9
6 10
5 844033520
8 780395612
2 285523486
6 13801767
3 487663185
3 667406485
7 672229269
7 207478896
5 769551740
7 806405364

Sample Output 3

665599367
675643489
193550820
987507475
230555342
555586355
204648376
83113599
299301383
545057926