20535번 - 최소 공통 조상과 쿼리

$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$