단조로운 보고 체계
다이아몬드 IV의견: 0
어떤 조직은 \(N\)명의 직원으로 이루어진 트리 구조의 보고 체계를 가진다. \(1\)번 직원이 최고 책임자(루트)이며, \(2\)번부터 \(N\)번까지 각 직원에게는 직속 상사가 한 명씩 있다.
직원 \(v\)는 현재 권한 등급 \(a_v\)를 가지고 있다. 조직은 등급을 새로 정하려 한다. 새 등급 \(b_v\)는 다음 조건을 만족해야 한다: 임의의 직원 \(v\)와 그의 직속 상사 \(p\)에 대해 \(b_v \ge b_p\) 여야 한다. 즉 루트에서 어떤 직원으로 내려가는 경로를 따라 등급이 감소하지 않아야 한다.
직원 \(v\)의 등급을 \(a_v\)에서 \(b_v\)로 바꾸는 비용은 \(|a_v - b_v|\) 이다. 모든 조건을 만족하면서 전체 비용의 합을 최소로 만들 때, 그 최솟값을 구하여라.
\(1 \le N \le 100{,}000\)
\(0 \le a_v \le 10^9\)
직속 상사 번호는 항상 자기 번호보다 작다 (트리가 보장된다).
첫 줄에 직원의 수 \(N\)이 주어진다.
다음 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
다음 줄에 \(N-1\)개의 정수가 주어지며, \(i\)번째 정수는 직원 \(i+1\)의 직속 상사 번호이다 (\(N=1\)이면 이 줄은 비어 있다).
조건을 만족하는 최소 비용의 합을 한 줄에 출력한다.
4
5 3 8 1
1 1 2
4루트(1)의 등급 5, 그 자식 2의 등급은 1이지만 5 이상이어야 하므로 올려야 한다. \(b=[3,3,3,8]\)로 잡으면 비용은 \(|5-3|+|1-3|+|3-3|+|8-8|=2+2+0+0=4\)로 최소이다.
3
5 3 1
1 2
4사슬 \(1\to2\to3\)에서 등급이 \(5,3,1\)로 감소한다. 모두 같은 값 \(3\)으로 맞추면 비용은 \(2+0+2=4\). 이보다 작게 만들 수 없다.
riseoj 작성
출처 Original
평가 및 의견
단조로운 보고 체계
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
단조로운 보고 체계