Informatica Online Judge

  파벌 싸움 [1693 / 069D]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 6   Total Tried : 6


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 박민솔)]

Background

총 N명의 사람들로 이루어진 GSHS국 정부는 트리 형태의 위계 질서가 유지되고 있다.

대통령은 1번이며, 대통령을 제외한 모든 사람들은 자기보다 번호가 작은 한 명의 직속 상관이 있다.

여기서 어떤 사람이 거느린 부하는, 자신의 직속 부하와 직속 부하들의 모든 부하들이라고 하자.


또한 GSHS국 정부에는 총 G개의 파벌이 있는데, 대통령을 포함한 모든 사람은 정확히 한 개의 파벌에 속해 있다.

또한 각 파벌마다 적어도 한 명의 사람이 존재한다.


최근 GSHS국 정부 내에 파벌 싸움이 심각해서 제대로 된 의사결정이 힘든 상황이다.

파벌끼리 권력을 잡기 위해서 서로를 헐뜯다보니 정작 국민을 위해서 목소리를 내는 파벌은 하나도 없다.

이에 대통령은 파벌 두 개씩을 차근차근 합병해서 서로 다른 의견을 가진 사람들을 줄이려는 계획을 세웠다.

허나 성향이 너무 다른 두 파벌을 합병하려다가는 더 큰 혼란을 초래할 수 있다.

그래서 일단 두 파벌의 친밀도를 계산하기로 하였다.


두 파벌 A와 B의 친밀도는 다음과 같이 정의된다.

- A에 속해 있는 사람 i와 B에 속해 있는 사람 j에 대해, i가 j의 부하이거나 j가 i의 부하인 (i,j)의 개수

즉, 부하/상관 관계가 많을수록 친밀도가 높다고 생각한 것이다.


대통령은 혼자의 힘으로 친밀도를 계산할 수 없다. 또한 대통령이 평소에 의지하던 비서 Siri는 구속되어서 도움을 청할 수도 없다.

여러분이 이 문제를 풀어서 무능한 대통령을 쫓아내고 GSHS국을 구한 위대한 대통령이 되어보자.

Input

첫 번째 줄에, 사람의 수 N과 파벌의 개수 G가 주어진다. (2<=N<=50,000), (2<=G<=N)

두 번째 줄에, N-1개의 수가 주어지는데, i번째 수 P_i는 i+1번 사람의 상관의 번호이다. (1<=P_i<=i)

세 번째 줄에, N개의 수가 주어지는데, i번째 수 C_i는 i번 사람이 속한 파벌의 번호이다. (1<=C_i<=G)

네 번째 줄에, 쿼리의 개수 Q가 주어진다. (1<=Q<=50,000)

다섯 번째 줄부터는 Q개의 쿼리가 한 줄에 하나씩 주어진다.

- 쿼리는 A B 꼴로 주어지는데, A번 파벌과 B번 파벌의 친밀도를 구하라는 쿼리이다. (1<=A<=N), (1<=B<=N), (A와 B는 다르다.)

Output

한 줄에 하나씩 각 쿼리에 대한 답을 순서대로 출력하면 된다.

IO Example

입력
10 3
1 2 2 3 3 4 4 1 1
2 1 1 3 2 3 1 1 3 2
3
1 2
1 3
2 3

출력
6
5
3

설명
첫 번째 쿼리 : (2,1), (2,5), (3,1), (3,5), (7,1), (8,1) 의 6개가 존재.
두 번째 쿼리 : (2,4), (2,6), (3,6), (7,4), (8,4) 의 5개가 존재.
세 번째 쿼리 : (1,4), (1,6), (1,9) 의 3개가 존재.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]