P15076 [ICPC 2024 Chengdu R] Disrupting Communications

敌人在多个地点建立了通信前哨站，这些站点可以表示为一个网络中的节点和边。该网络形成一棵**树**——这是一种连通且无环的图。作为一名通信工程专家，你的任务是破坏他们的通信。 每次通信发生在树中两个节点之间的一条简单路径上。你有能力选择这棵树的一个子图，并破坏该子图中的每个节点。如果通信路径包含一个被破坏的节点，则该通信被成功破坏。你选择的子图必须由原树的一个节点和边的子集构成，并且它必须是连通的，即它本身也是一棵树。 通信网络包含 $n$ 个节点，编号从 $1$ 到 $n$。你的任务包括回答 $q$ 个独立的查询。对于每个查询，给定两个节点 $u_i$ 和 $v_i$，你必须确定可以选择多少种不同的子图来破坏这两个节点之间的通信。由于数量可能非常大，你应该输出答案对 $998244353$ 取模的结果。可能出现 $u_i = v_i$ 的情况，这表示节点内部的通信，你也可以通过选择一个包含该节点的子图来破坏它。

- 第一行包含一个整数 $T$（$1\le T \le 10^4$），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $n$（$2\le n\le 10^5$）和 $q$（$1\le q \le 10^5$），分别表示节点数量和查询数量。 - 第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1\le p_i < i$），表示节点 $i$ 和 $p_i$ 之间由一条边连接。 - 接下来的 $q$ 行，每行包含两个整数 $u_i, v_i$（$1\le u_i, v_i \le n$），表示第 $i$ 个查询。 保证所有测试用例的 $n$ 之和以及 $q$ 之和分别不超过 $3 \cdot 10^5$。

对于每个测试用例，输出 $q$ 行，每行包含一个查询的结果，对 $998244353$ 取模。

在示例的第一个测试用例中，总共可以选择 $6$ 个连通子图。对于第一个查询，所有这些子图都能破坏通信。对于第二个查询，其中有 $5$ 个子图可以破坏通信；例外是仅包含节点 $3$ 的子图。 翻译由 DeepSeek V3 完成