페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5300

방문하면 우는 소 (Visit) 2초 1024MB

문제

미스횡성을 3년 연속 1등한 횡성에서 제일 아름다운 소 김횡성양은 본인의 농장을 소유하고 있습니다.

그녀의 다른 소 친구 N마리(2≤N≤​10^5)​는 각각 1...N번으로 번호가 붙어있으며, 그들도 모두 각자 ​자신의 농장을 소유하고 있습니다.

 

친구들은 모두 사교성이 뛰어난 소들이라서 모두 방문하길 희망하는 친구가 있습니다.​ 

i번 친구는 a_i(a_i \ne i)번 친구를 방문하기를 원하는데, 1...N의 순열(p_1, p_2, ... ,p_N)이 주어지면 방문은 다음과 같이 발생합니다.

 

1부터 N까지의 i에 대해:

 - 친구 a_{pi}가 이미 본인의 농장을 떠났다면, 친구 p_i는 자신의 농장에 남아있다.

 - 그렇지 않으면, 친구 p_i가 자신의 농장을 떠나 친구 a_{pi}의 농장을 방문한다. 이 경우 소가 v_{pi}번 즐겁게 울음소리를 낸다. (0≤v_{pi}≤10^9).

 

이 때, 모든 경우의 순열 p에 대해 모든 방문이 끝난 후, 최대 울음소리의 수를 출력하는 프로그램을 작성하시오.​ 


입력

첫 번째 줄에 N이 입력된다.

두 번째 줄에서부터 N줄에 걸쳐 a_i와 v_i가 공백을 기준으로 입력된다. (1≤​i≤​N)​


출력

모든 경우의 순열 p에 대해 모든 방문이 끝난 후, 최대 울음소리의 수를 출력​하시오.

이 문제와 관련된 큰 크기의 정수는 64비트 정수 데이터 유형(예: C/C++의 "long long")을 사용해야 할 수 있다.


예제1

입력
4

2 10

3 20

4 30

1 40
출력
90

만약 p가 (1, 4, 3, 2)라면,

​-친구 1은 친구 2의 농장을 방문하고, 10번의 울음소리가 발생한다.

-친구 4는 친구 1이 이미 떠난 것을 확인하고 아무 일도 일어나지 않는다.

​-친구 3은 친구 4의 농장을 방문하고, 30번의 울음소리가 발생한다.

-친구 2는 친구 3이 이미 떠난 것을 확인하고 아무 일도 일어나지 않는다.

이 경우 10+30=40으로 총 40번의 울음소리가 발생한다.​

 

하지만 만약 p가 (2, 3, 4, 1)이라면,

-​친구 2은 친구 3의 농장을 방문하고, 20번의 울음소리가 발생한다.

-친구 3은 친구 4의 농장을 방문하고, 30번의 울음소리가 발생한다.

-친구 4은 친구 1의 농장을 방문하고, 40번의 울음소리가 발생한다.

-친구 1는 친구 2이 이미 떠난 것을 확인하고 아무 일도 일어나지 않는다.

이 경우 20+30+40=90으로 총 90번의 울음소리가 발생한다.​


예제2

입력
6
4 10
5 4
4 3
3 10
6 4
1 1
출력
29

예제3

입력
3
3 2
3 5
1 3
출력
8

출처

USACO 2022 US Open Silver

역링크 공식 문제집만