AT_ndpc2026_t 独立集合
题目描述
给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。
如果集合 $S$ 满足以下条件，则称为**独立集**：
- 对于任意不同的顶点 $u, v \in S$，$u$ 和 $v$ 在树中没有直接相连。
对于一个顶点 $v$，定义 $F_v$ 为所有满足 $v \in S$ 的独立集 $S$ 的集合。
你会得到 $Q$ 个询问。每个询问给定一个整数 $v \ (1 \leq v \leq N)$ 和整数 $q$。请计算：
$$
\left( \sum_{S \in F_v} q^{|S|} \right) \bmod 998244353
$$
其中 $|S|$ 为集合 $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$
> $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$ 个询问的答案。
说明/提示
## 部分分数
本题设置了部分得分。
- 如果所有询问满足 $v=1$，可以获得 $5$ 分。
## 样例解释 1
考虑第一个询问。包含顶点 $1$ 的独立集有 $\{1\}$ 和 $\{1, 4\}$，因此总共 $2$ 个集合。于是输出 $1^1 + 1^2 = 2$。
## 数据范围
- $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$
- 所有输入值均为整数
由 ChatGPT 5 翻译