왕국의 인구 조사
다이아몬드 I의견: 0
\(N\)개의 정점으로 이루어진 트리가 있다. 정점은 \(1\)번부터 \(N\)번까지 번호가 매겨져 있으며 \(1\)번 정점이 루트이다. 각 정점 \(v\)에는 색 \(c_v\)와 정수 \(k_v\)가 적혀 있다.
정점 \(v\)의 서브트리란 \(v\)를 루트로 하는 부분 트리(자기 자신 포함)를 말한다.
모든 정점 \(v\)에 대해, \(v\)의 서브트리에 속한 정점들의 색만 모았을 때 \(k_v\)번 이상 등장하는 서로 다른 색의 개수를 구하라.
즉 각 정점마다 자신의 서브트리 안에서 등장 횟수가 \(k_v\) 이상인 색이 몇 종류인지를 답해야 한다.
\(1 \le N \le 100{,}000\)
\(1 \le c_v \le N\)
\(1 \le k_v \le N\)
첫 줄에 정점의 수 \(N\)이 주어진다.
둘째 줄에 \(N-1\)개의 정수가 주어지며, \(i\)번째 수는 정점 \(i+1\)의 부모 번호이다 (부모 번호는 항상 자식보다 작은 번호를 가진다).
셋째 줄에 \(N\)개의 정수 \(c_1, \dots, c_N\)이 주어진다.
넷째 줄에 \(N\)개의 정수 \(k_1, \dots, k_N\)이 주어진다.
한 줄에 \(N\)개의 정수를 공백으로 구분하여 출력한다. \(v\)번째 수는 정점 \(v\)에 대한 답이다.
5
1 1 2 2
1 2 1 2 2
2 1 1 1 1
2 1 1 1 1정점1의 서브트리 색: {1,2,1,2,2} = 색1이 2번, 색2가 3번. k_1=2이므로 둘 다 2회 이상 -> 2. 정점2의 서브트리 색: {2,2,2}, k_2=1 -> 색2 한 종류 -> 1. 정점3,4,5는 잎이며 각 k=1이므로 모두 1.
3
1 2
3 3 1
2 1 1
1 2 1정점1 서브트리 색 {3,3,1}: 색3이 2회, 색1이 1회. k_1=2 -> 색3만 -> 1. 정점2 서브트리 {3,1}: k_2=1 -> 두 종류 -> 2. 정점3은 잎 -> 1.
riseoj 작성
출처 Original
평가 및 의견
왕국의 인구 조사
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
왕국의 인구 조사