P15076 [ICPC 2024 Chengdu R] Disrupting Communications

The enemy has established communication outposts across several locations, which can be represented as nodes and edges in a network. This network forms a tree --- a type of graph that is connected and has no cycles. As a specialist in communications engineering, your task is to disrupt their communications. Each communication occurs along a simple path between two nodes in the tree. You have the ability to select a subgraph of this tree and disrupt every node in that subgraph. If the communication path includes a disrupted node, the communication is successfully disrupted. The subgraph you select must consist of a subset of nodes and edges from the original tree, and it must be connected, meaning it is also a tree. The communication network consists of $n$ nodes, labeled from $1$ to $n$. Your mission involves answering $q$ separate queries. For each query, you are given two nodes, $u_i$ and $v_i$, and you must determine how many different subgraphs you can select to disrupt the communication between the two nodes. Since the number may be very large, you should provide the answer modulo $998244353$. It is possible that $u_i=v_i$, which indicates an internal communication within a node, and you are also able to disrupt it by selecting a subgraph that contains the node.

The first line contains a single integer $T$ ($1\le T \le 10^4$), indicating the number of test cases. The first line of each test case contains two integers $n$ ($2\le n\le 10^5$) and $q$ ($1\le q \le 10^5$), denoting the number of nodes and the number of queries. The second line contains $n-1$ integers $p_2,p_3,\ldots ,p_n$ ($1\le p_i < i$), indicating that nodes $i$ and $p_i$ are connected by an edge. Each of the next $q$ lines contains two integers $u_i,v_i$ ($1\le u_i,v_i \le n$), representing the $i$-th query. It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $3\cdot 10^5$, respectively.

For each test case, output $q$ lines, each containing the result modulo $998244353$ for one of the $q$ queries.

In the first case of the example, $6$ connected subgraphs can be selected in total. For the first query, all of them can disrupt the communication. For the second query, $5$ of them can disrupt the communication; the exception is the subgraph consisting only of node $3$.