← 返回题目列表

AtCoder · ndpc2026_t

T. 独立设置

中文机器翻译题面 查看原题

分数: 10 点

问题陈述

你有一棵树 N 顶点,编号自 1 to N。的 i第一条边连接顶点 u_i 和 v_i.

一组顶点 S 被称为 独立套装 如果满足以下条件:

  • 对于任意两个不同的顶点 u, v \in S, u 和 v 在树中不相邻。

对于顶点 v,让 F_v 是所有独立集合的集合 S 这样 v \in S.

你被给予 Q 查询。在每个查询中,您都会得到一个整数 v (1 \leq v \leq N)和一个整数 q。计算:

\displaystyle \left( \sum_{S \in F_v} q^{|S|}\right) \bmod 998244353

在这里, |S| 表示集合的大小 S.

约束

  • 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
  • 给定的图是一棵树
  • 1 \leq v \leq N
  • 1 \leq q < 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} 和 {1, 4},所以有 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