레이팅 미적용소들이 또다시 스타트업 회사를 차리려 하고 있다. 소는 형편없는 관리자가 된다는 과거의 경험을 까맣게 잊은 것이다!
소들은 편의상 \(1 \ldots N\)번으로 번호가 매겨져 있으며 (\(1 \leq N \leq 100,000\)), 회사를 트리 형태로 조직하고 소 1번이 사장(트리의 루트)을 맡는다. 사장을 제외한 각 소는 정확히 한 명의 관리자(트리에서의 "부모")를 갖는다. 각 소 \(i\)는 서로 다른 업무 능력치 \(p(i)\)를 가지며, 이는 그 소가 일을 얼마나 잘하는지를 나타낸다. 소 \(i\)가 소 \(j\)의 조상(예: 관리자의 관리자의 관리자)이라면, \(j\)는 \(i\)의 부하라고 한다.
안타깝게도 소들은 관리자가 자신의 여러 부하보다 능력치가 낮은 경우가 흔하다는 사실을 알게 되었고, 이런 경우 관리자는 부하 중 일부의 승진을 고려해야 한다. 당신의 임무는 이런 일이 언제 일어나는지 소들이 파악하도록 돕는 것이다. 회사의 각 소 \(i\)에 대해, \(p(j) > p(i)\)인 부하 \(j\)의 수를 세시오.
문제 출처: Karthik Nair
문제 출처: Karthik Nair
입력의 첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 소들의 업무 능력치 \(p(1) \ldots p(N)\)이 주어진다. 각각은 \(1 \ldots 1,000,000,000\) 범위의 서로 다른 정수이다.
다음 \(N-1\)개의 줄은 소 \(2 \ldots N\)의 관리자(부모)를 나타낸다. 소 1번은 사장이므로 관리자가 없음을 기억하자.
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 소 \(i\)보다 능력치가 높은, 소 \(i\)의 부하의 수를 출력한다.
promote.in · 출력을 쓸 파일 promote.out5
804289384
846930887
681692778
714636916
957747794
1
1
2
32
0
1
0
0riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > January > Platinum