IOI 2014- 친구들 > 문제은행 : 정보올림피아드&알고리즘




3603 : 친구들

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
7 회   
시도횟수
9 회   

문제

0, ... , N−1 로 번호가 매겨진 N명의 사람으로 구성된 소셜 네트워크를 만들자. 이 네트워크에 있는 사람들 중 어떤 쌍은 서로 친구가 된다. 즉, 사람 x가 사람 y의 친구가 되면, 사람 y도 사람 x의 친구가 된다.

 

사람들은 N단계를 거쳐서 네트워크에 추가되는데, 각 단계를 0부터 N−1로 번호를 매기자. 사람 i는 단계 i에 추가된다. 단계 0에서, 사람 0은 이 네트워크에 있는 유일한 사람으로 추가된다. 다음 N−1개의 각 단계에서, 초대자가 새로 사람 하나를 네트워크에 추가한다. 초대자는 이 단계에 네트워크에 이미 들어와 있는 사람 중 하나이다. 단계 i에서 (0<i<N), 이 단계의 초대자는 새로 들어오는 사람 i를 다음 프로토콜 중 하나를 사용하여 네트워크에 추가한다.

 

IAmYourFriend는 사람 i를 초대자의 친구로만 등록한다.

MyFriendsAreYourFriends는 사람 i를 초대자의 현재 모든 친구의 친구로 등록한다. 이 경우 사람 i는 초대자의 친구가 아니다.

WeAreYourFriends는 사람 i를 초대자와, 초대자의 현재 모든 친구의 친구로 등록한다.

 

네트워크를 다 만든 다음에는 설문을 위해서 표본을 구하고자 한다. 표본은 네트워크에 속한 사람들로 구성된 모임이다. 친구끼리는 서로 좋아하는 것이 비슷하기 때문에, 표본에 속하는 사람들 중에는 서로 친구인 쌍이 있으면 안된다. 각 사람마다 설문에서 쓰이는 신뢰도가 있는데, 이는 양의 정수로 표현된다. 우리는 신뢰도의 총합이 최대인 표본을 구하려 한다.

 

N=6명의 사람들이 다음과 같은 방식으로 네트워크에 추가된다고 하자.​

 

 

처음 네트워크에는 사람 0만 있다. 단계 1의 초대자(사람 0)는 새로 사람 1을 IAmYourFriend 프로토콜로 추가해서, 서로 친구가 된다. 단계 2의 초대자(이번에도 사람 0)는 사람 2를 MyFriendsAreYourFriends로 추가하는데,사람 1(초대자의 유일한 친구)이 사람 2의 유일한 친구가 된다. 단계 3의 초대자(사람 1)는 사람 3을 WeAreYourFriends로 추가하는데, 사람 3은 사람 1(초대자)과 사람 0, 2 (초대자의 친구들)의 친구가 된다. 단계 4와 단계 5도 표에 보인 바와 같다. 최종적인 네트워크는 다음 그림과 같고, 동그라미 안의 숫자는 사람의 번호이고, 동그라미 아래의 숫자는 이 사람의 신뢰도를 나타낸다. 사람 3과 5로 이루어진 표본의 신뢰도의 총합은 20 + 15 = 35인데, 이는 가능한 신뢰도의 총합 중 최대이다.

 



친구 관계가 추가되는 방식이 주어지면 신뢰도의 총합이 최대인 표본을 구하는 프로그램을 작성하여라.

 


입력형식

첫 번째 줄에는 사람의 수 N가 주어진다.

 

두 번째 줄에는 0, …, N-1번 사람의 신뢰도가 주어진다.

 

세 번째 줄에는 2N-2개의 정수가 주어진다. 2i-1번째 정수는 i번 사람의 초대자를, 2i번째 정수는 i번 사람의 프로토콜을 의미한다. (0이면 IAmYourFriend, 1이면 MyFriendsAreYourFriends, 2이면 WeAreYourFriends)

 

모든 데이터는 2 ≤ N ≤ 100,000과 1 ≤ 신뢰도 ≤ 10,000를 만족하거나 2 ≤ N ≤ 1,000과 1 ≤ 신뢰도 ≤ 1,000,000를 만족한다.

 


출력형식

첫 번째 줄에 만들 수 있는 최대 신뢰도를 출력한다.

 


입력 예

6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0

출력 예

35

출처

IOI 2014

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP