16002번 - 조용한 생활관 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 (추가 시간 없음) | 768 MB | 257 | 39 | 25 | 16.447% |
문제
카카오 마법 학교는 건물들의 독특한 구조로 유명한데, 그중에서도 특이한 것은 학생 생활관이다. 카카오 마법 학교의 생활관은 N 개의 건물로 이루어져 있으며, N-1 개의 도로가 건물 사이를 잇고 있다. 특이한 것은 이 도로들이 모두 일방통행이라는 것이다. 자세한 구조를 설명하자면, 생활관은 입구와 출구가 있으며, 입구에는 1번 건물이 있다. 1번 건물을 제외한 각 건물에는 그 건물로 들어오는 도로가 정확히 하나 존재하며, 1번 건물로부터 각 건물까지 일방통행 도로만을 이용해서 갈 수 있다. 그리고 모든 건물에서 출구로 가는 길이 존재하는데, 생활관 규칙이 엄격하여 밤에는 출구가 폐쇄된다.
라이언은 카카오 마법 학교에서 코딩마법을 가르치는 교수이다. 요즘 그의 가장 큰 고민거리는 교수아파트 바로 옆에 있는 학생 생활관에서 발생하는 소음 때문에 잠을 이루지 못한다는 것이다. 생활관이 이렇게 시끄러운 이유는 많은 학생이 한 건물로 모여들기 때문이다. 라이언 교수는 두 도로를 이어서 한 도로로 만드는 ‘Union’ 마법을 이용해서 원래 서로 오고 갈 수 있던 건물들을 그렇지 못하게 만들어 학생들이 모이는 것을 방지하고자 한다. ‘Union’ 마법을 자세히 설명하면, 한 도로의 끝점과 다른 도로의 시작점이 같을 때 두 도로를 이어 붙이는 마법이다. 즉, 한 도로가 건물 x 에서 건물 y 로, 다른 도로가 건물 y 에서 건물 z 로 가는 도로일 때 ‘Union’ 마법을 사용하면 원래 있던 두 도로는 사라지고 건물 x 에서 z 로 가는 하나의 도로가 생긴다. 이때, 새 도로는 건물 y 를 지나지 않는다.
라이언의 목표는 생활관의 “시끄러운 정도”를 최소화하는 것이다. 생활관의 “시끄러운 정도”는 서로 다른 건물에 사는 학생 a 와 학생 b 에 대해, 학생 a 가 사는 건물에서 학생 b 가 거주하는 건물로 가는 경로가 존재하는 (a, b) 쌍의 개수이다. 앞서 말했다시피 밤에는 출구가 폐쇄되기 때문에 출구로 나갔다가 입구로 다시 들어오는 것은 불가능하다.
라이언은 오랜 기간 마법을 수련해 무제한으로 ‘Union’ 마법을 사용할 수 있다. 이때, 생활관의 “시끄러운 정도”의 가능한 최솟값을 구해 라이언을 도와주자.
입력
입력의 첫째 줄에는 생활관의 건물 개수 N(2 ≤ N ≤ 200,000)이 주어진다. 다음 줄에는 N-1 개의 수가 공백을 사이에 두고 주어진다.
N-1 개의 수 중 i 번째 수는 i+1 번째 건물로 가는 일방통행 도로의 시작점에 있는 건물의 번호이다.
다음 줄에는 각 건물에 사는 학생의 수를 나타내는 N 개의 수가 공백을 사이에 두고 주어진다. 한 건물에 사는 학생의 수는 1 이상 106 이하이다.
출력
첫 번째 줄에 생활관의 “시끄러운 정도”의 가능한 최솟값을 출력한다.
예제 입력 1
4 1 1 2 2 1 3 2
예제 출력 1
10
도로 (1, 2)와 (2, 4)를 이으면 건물 1에서 건물 4로, 건물 1에서 건물 3으로 갈 수 있으므로 생활관의 시끄러운 정도는 2*2 + 2*3 = 10이 된다.
출처
Contest > 카카오 코드 페스티벌 > 카카오 코드 페스티벌 2018 F번
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 2: GP of ainta D번
- 문제를 만든 사람: ainta
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호