Static Query on Tree

In country X, there are $n$ cities and $n - 1$ one-way roads, and all city can reach city 1. One query will give 3 sets of cities A, B, C. Alice will choose a city x in set A, choose a city z in set C, and walk from x to z (if x can reach z). Bob will choose a city y in set B, and walk from y to z (if y can reach z). How many cities can possibly be the city where Alice and Bob meet each other?

In other words, how many cities can be reached from at least one city in set A, and can be reached from at least one city in set B, and can reach at least one city in set C?

There are $T$ test cases, and each case has $q$ queries.

First line is one integer $T$, indicating $T$ test cases. In each case:

First line is 2 integers $n, q$, indicating $n$ cities and $q$ queries.

Next line is $n - 1$ integers $r_1, r_2, \ldots, r_{n-1}$, the $i$-th integer indicates the road from city $i + 1$ to city $r_i$.

Next is $q$ queries, in each query:

First line is 3 integer $|A|,|B|,|C|$, indicating the size of set A, B, C.

Next line is $|A|$ integers, indicating the set $A$.

Next line is $|B|$ integers, indicating the set $B$.

Next line is $|C|$ integers, indicating the set $C$.

$1 \le T \le 20,$ $1\le n, q, |A|, |B|, |C| \le 2\times 10^5,$ for all cases $\sum n\le 2\times 10^5,$ $\sum q\le 2\times 10^5,$ for all queries in all cases $\sum |A|+\sum |B|+\sum|C|\le 2\times 10^5$.

In each case, print $q$ integers, one integer per line, $i$-th integer indicates the answer of $i$-th query.

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

2
4
1

For the first query, city 1, 2.
(1 can be reached from 1 (A), 4 (B), can reach 1(C))
(2 can be reached from 2 (A), 4 (B), can reach 1(C))
For the second query, city 2, 4, 5, 6.
For the third query, only city 1.

2022“杭电杯”中国大学生算法设计超级联赛（2）