최소 공통 조상과 쿼리

시간 제한5초메모리 제한1536 MB

요약

루트가 1인 트리에서 각 질의의 K개 정점을 받아 모든 쌍의 LCA 레벨을 더한 값을 구합니다.

문제

$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$ 가 공백으로 구분되어 주어진다.

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

예제 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

예상 출력