Dynamic Tree Beauty - Repovive Starter Round 2 | Repovive

10G. Dynamic Tree Beauty

3500 pts2s512 MB

You are given a rooted tree with $n$ vertices, numbered from $1$ to $n$ . The root is vertex $1$ .

For every vertex $i$ with $2 \le i \le n$ , you are given its parent $p_i$ . It is guaranteed that $1 \le p_i < i$ . The parents $p_2,p_3,\ldots,p_n$ are given in one line.

At first, only vertex $1$ is red, and all other vertices are white. Vertex $1$ always remains red.

You are given $q$ queries. The query vertices $x_1,x_2,\ldots,x_q$ are given in a single line. In each query, a vertex $x$ with $2 \le x \le n$ is given. If vertex $x$ is white, it becomes red. If vertex $x$ is red, it becomes white.

After each query, consider all ways to choose some of the white vertices and color them blue. If there are $w$ white vertices, there are $2^w$ such choices.

For each choice, define the colored vertices as all vertices that are red or blue. The blue coloring is only used for this calculation and is not kept for later queries.

The beauty of the tree is the minimum number of edges that must be marked so that, using only marked edges, it is possible to move between every pair of colored vertices. If there is only one colored vertex, the beauty is $0$ .

After each query, output the sum of the beauties over all choices of blue vertices, modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le q \le 2 \times 10^5$
$1 \le p_i < i$
$2 \le x \le n$ for each query
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $q$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad q \\ p_2 \quad p_3 \quad \cdots \quad p_n \\ x_1 \quad x_2 \quad \cdots \quad x_q \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_q \end{array} \right\} \times t

Samples

Input

Case 1

2 3
1
2 2 2

Case 2

3 3
1 2
2 3 2

Case 3

4 4
1 1 1
2 3 2 4

Case 4

5 4
1 1 3 3
4 5 2 4

Case 5

6 5
1 1 2 2 3
4 6 5 6 2

Explanation

Case 1

There is only one non-root vertex. After each query, either it is red or it is the only vertex that may become blue, so the sum is always $1$ .

Case 2

After vertex $2$ becomes red, choosing vertex $3$ as blue or not gives beauties $2$ and $1$ . After vertex $3$ also becomes red, both edges are needed. After vertex $2$ becomes white again, the path between vertices $1$ and $3$ still uses both edges in every blue choice.

Case 3

The tree is a star centered at vertex $1$ . The beauty is exactly the number of colored leaves, so each query changes which leaves are already forced to be colored.

Case 4

After the first query, vertex $4$ is red. For example, if neither vertex $2$ nor vertex $5$ is blue, the marked edges are the two edges on the path from $1$ to $4$ . Summing over all blue choices gives the printed values.

Case 5

In the last query, vertex $2$ becomes red. Then vertices $1,2,4,5$ are red, and vertices $3,6$ are white. The four possible blue choices have beauties $3,5,4,5$ , so the sum is $17$ .

Output

Case 1

1 1 1

Case 2

3 2 4

Case 3

8 5 8 5

Case 4

24 14 8 14

Case 5

60 36 20 34 17

You are given a rooted tree with $n$ vertices, numbered from $1$ to $n$ . The root is vertex $1$ .

For every vertex $i$ with $2 \le i \le n$ , you are given its parent $p_i$ . It is guaranteed that $1 \le p_i < i$ . The parents $p_2,p_3,\ldots,p_n$ are given in one line.

At first, only vertex $1$ is red, and all other vertices are white. Vertex $1$ always remains red.

After each query, consider all ways to choose some of the white vertices and color them blue. If there are $w$ white vertices, there are $2^w$ such choices.

For each choice, define the colored vertices as all vertices that are red or blue. The blue coloring is only used for this calculation and is not kept for later queries.

After each query, output the sum of the beauties over all choices of blue vertices, modulo $998244353$ .

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le q \le 2 \times 10^5$
$1 \le p_i < i$
$2 \le x \le n$ for each query
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $q$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad q \\ p_2 \quad p_3 \quad \cdots \quad p_n \\ x_1 \quad x_2 \quad \cdots \quad x_q \end{array} \right\} \times t

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_q \end{array} \right\} \times t

There is only one non-root vertex. After each query, either it is red or it is the only vertex that may become blue, so the sum is always $1$ .

The tree is a star centered at vertex $1$ . The beauty is exactly the number of colored leaves, so each query changes which leaves are already forced to be colored.

In the last query, vertex $2$ becomes red. Then vertices $1,2,4,5$ are red, and vertices $3,6$ are white. The four possible blue choices have beauties $3,5,4,5$ , so the sum is $17$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

10G. Dynamic Tree Beauty

Constraints

Input

Output

Samples

10G. Dynamic Tree Beauty

Constraints

Input

Output

Samples