分数: 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