RiseOJ – Friend

설명

A social network of $$n$$ people (numbered $0 \dots n-1$ ) is built one person at a time. Person $$0$$ is added first. For $i = 1 \dots n-1$ , person $$i$$ is added by a host $$h_i$$ ( $0 \le h_i < i$ ) using one of three protocols:

0 — IAmYourFriend: $$i$$ becomes a friend of $$h_i$$ .
1 — MyFriendsAreYourFriends: $$i$$ becomes a friend of every current friend of $$h_i$$ (but not of $$h_i$$ ).
2 — WeAreYourFriends: $$i$$ becomes a friend of $$h_i$$ and of every current friend of $$h_i$$ .

Each person $$i$$ has a confidence value $$c_i$$ . A sample is a set of people that are pairwise not friends. Output the maximum possible total confidence of a sample.

Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.

Interaction / I/O protocol

Input. Line 1: $$n$$ . Line 2: $$n$$ integers $c_0 \dots c_{n-1}$ . Then $$n-1$$ lines; line $$i$$ (for $i = 1 \dots n-1$ ) contains $$h_i$$ and the protocol $p_i \in \{0,1,2\}$ .

Output. Print one integer: the maximum total confidence of a sample.

Example. n=6, confidences 1 3 5 2 4 6, additions (h,p): (0,0) (0,2) (1,1) (1,0) (2,2) give a maximum sample confidence of 10.

제약

$1 \le n \le 100{,}000$
$1 \le c_i \le 1000$
$0 \le h_i < i$ , $\; p_i \in \{0,1,2\}$

입력 형식

Line 1: $$n$$ . Line 2: $$n$$ integers $c_0 \dots c_{n-1}$ . Then $$n-1$$ lines; line $$i$$ (for $i = 1 \dots n-1$ ) contains $$h_i$$ and the protocol $p_i \in \{0,1,2\}$ .

출력 형식

Print one integer: the maximum total confidence of a sample.

인터랙티브 문제

프로그램이 고정된 입력을 읽는 대신 표준 입출력으로 채점기와 메시지를 주고받습니다. 한 줄을 출력할 때마다 표준 출력을 flush하고(예: cout에 endl / print(..., flush=True) / System.out.flush()), 채점기의 응답을 읽으세요. 파일을 읽거나 쓰면 안 됩니다.

문제 정보

rip 작성

출처 IOI 2014

올림피아드 > IOI > 2014

Friend

Interaction / I/O protocol

평가 및 의견

풀이 제출