AT_ndpc2026_t.Independent Set

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$.

给你一棵包含 $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$，请计算：

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

其中，$|S|$ 表示集合 $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$

输入从标准输入中按以下格式给出：

$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$

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

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

Partial Score

This problem has partial scoring.

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

Sample 1 Explanation:
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

部分得分

本题采用部分得分制。

• 若所有查询均满足 $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$
• 所有输入值均为整数