경로 위 서로 다른 색의 수
다이아몬드 V의견: 0
\(N\)개의 정점으로 이루어진 트리가 있다. 각 정점 \(i\)에는 색 \(c_i\)가 칠해져 있다.
\(Q\)개의 질의가 주어진다. 각 질의는 두 정점 \(u\), \(v\)로 이루어지며, \(u\)에서 \(v\)로 가는 (트리에서 유일한) 경로 위에 놓인 정점들의 색 중 서로 다른 색의 가짓수를 구해야 한다. 경로에는 \(u\)와 \(v\) 자신도 포함된다.
정점 수와 질의 수가 매우 크므로 각 질의를 따로 처리하는 풀이는 통과할 수 없다.
\(1 \le N \le 50{,}000\)
\(1 \le Q \le 50{,}000\)
\(1 \le c_i \le 10^9\)
\(1 \le a, b, u, v \le N\)
첫째 줄에 정점 수 \(N\)과 질의 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 색 \(c_1, \dots, c_N\)이 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 트리의 간선 정보 \(a\), \(b\)가 주어진다 (정점 \(a\)와 \(b\)를 잇는 간선).
다음 \(Q\)개의 줄에 각 질의의 \(u\), \(v\)가 주어진다.
각 질의에 대해 경로 위 서로 다른 색의 가짓수를 한 줄에 하나씩 출력한다.
5 3
1 2 1 3 2
2 1
3 1
4 2
5 2
4 5
3 4
1 1
2
3
1트리: 1-2, 1-3, 2-4, 2-5. 색 \(c=[1,2,1,3,2]\). 경로 4→5는 4,2,5로 색 \(\{3,2,2\}\) → 2가지. 경로 3→4는 3,1,2,4로 색 \(\{1,1,2,3\}\) → 3가지. 경로 1→1은 정점 1뿐 → 1가지.
4 2
5 5 7 5
2 1
3 2
4 3
1 4
1 2
2
1사슬 1-2-3-4, 색 \([5,5,7,5]\). 경로 1→4의 색 \(\{5,5,7,5\}\) → 2가지. 경로 1→2의 색 \(\{5,5\}\) → 1가지.
riseoj 작성
출처 Original
평가 및 의견
경로 위 서로 다른 색의 수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경로 위 서로 다른 색의 수