시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1536 MB 124 60 48 59.259%

문제

$N$개의 정점으로 이루어져 있는 트리 $T$가 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • $K \ V_1 \ V_2 \ \cdots \ V_K$ : $1 \leq i < j \leq K$인 모든 $(i, j)$ 쌍에 대해 $V_i$번 정점과 $V_j$번 정점의 LCA의 레벨의 합을 출력한다.

$T$의 루트 정점은 1번 정점이다. 루트 정점의 레벨은 0이며, 다른 정점의 레벨은 (부모 정점의 레벨) + 1로 정의한다.

두 정점 $u, v$의 LCA는 $u, v$의 공통 조상 중 가장 가까운 정점(최소 공통 조상)을 의미한다.

입력

첫째 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 주어진다.

둘째 줄에는 $2, 3, \cdots, N$번 정점의 부모 정점을 나타내는 자연수 $P_2, P_3, \cdots, P_N$이 주어진다.

다음 $Q$개의 줄에는 쿼리를 나타내는 $K \ V_1 \ V_2 \ \cdots \ V_K$가 공백으로 구분되어 주어진다.

출력

각각의 쿼리마다 한 줄에 하나씩 결과를 출력한다.

제한

  • $2 \leq N \leq 500\,000$
  • $1 \leq Q \leq 500\,000$
  • $2 \le i \le N$에 대해 $1 \le P_i < i$
  • $2 \leq K \leq N$
  • (모든 쿼리에서 $K$의 합) $\leq 1\,000\,000$
  • $1 \leq V_i \leq N$
  • $i \ne j$ 이면 $V_i \ne V_j$

예제 입력 1

16 4
1 2 3 4 3 1 7 8 9 7 11 12 1 14 15
2 4 5
2 10 13
3 4 6 16
4 4 10 6 13

예제 출력 1

3
1
2
3

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2020! G번