Informatica Online Judge

  전나무 아래에서 [2138 / 085A]

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


The Champion of this Problem (C++) : gs16109 - 16ms / 1224byte
My Best Submission (C++) : N/A

[34th 정원준]
Writer ID : [gs16103]

Background

호랑이와 용이 크리스마스를 기념하여 트리를 조립했다.

트리는 상하 관계가 있는 트리 모양으로 생겼고, 트리의 각 노드는 부품, 간선은 연결 관계를 의미한다.

어떤 부품 아래에 다른 부품을 붙이는 것은 어렵기 때문에 이를 조립하기 위해서는 아래에서부터 위로 조립해야 한다. 조립이란, 다음과 같이 설명 가능하다.

- 한 개의 상위 부품이 있고, 그 아래에 연결되는 모든 부분이 완성되었을 때, 상위 부품과 아래의 부품들을 한 번에 연결한다. -



또한 각 조립당 드는 시간은 조립하는 모든 부품의 무게의 합이다.

트리를 다 조립해서 기뻐하고 있는 것도 잠시, 밖에서 창문을 깨고 날아온 소프트볼 하나가 트리의 한 연결 부분을 부쉈다.

호랑이와 용은 매우 착하기 때문에 부순 범인을 나무라지 않고 트리를 다시 복원하려 한다. 트리를 조립하는 규칙 때문에, 트리를 조금 더 부숴야 복원이 가능할 수도 있다.

부수는 것은 호랑이가 순식간에 해준다고 할 때, 트리를 복원하는 데 드는 시간을 구하여라.

단, 트리의 맨 위에는 별 장식이 달려있고, 별 장식이 부서진 경우에는 충격에 빠진 나머지, 호랑이가 트리를 순식간에 전부 부수기 때문에 다시 처음부터 조립해야 한다.

Input

첫 줄에 부품의 수 N, 소프트볼이 날아오는 횟수 Q가 주어진다.
( 1<=N<=200000, 1<=Q<=200000 )

두 번째 줄에 부품의 무게 Wi ( i = 1,2,…N ) 가 주어진다. ( 1<=Wi<=1000 )

세 번째 줄에 2번 노드부터 N번 노드까지의 각 노드(부품)의 부모 노드가 주어진다.
루트 노드는 1번으로 고정된다.

네 번째 줄에 소프트볼에 의해 부서진 간선의 아래쪽 노드의 번호가 Q개 주어진다. 번호가 1인 경우에는, 별 장식이 부서진 경우로 본다.

각 문제는 독립적인 문제로, 트리가 부서진 후에는 다시 복원이 되어야 새로운 소프트볼이 트리를 부순다.

Output

Q개의 쿼리에 대해, 복원에 필요한 시간을 공백을 사이에 두고 출력한다.

IO Example

입력
6 3
3 2 1 2 1 3
1 1 2 3 3
3 5 1

출력
12 17 21

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