24914번 - Split the SSHS 서브태스크

문제

서울의 명소 서울과학고등학교에는 1부터 N까지의 번호가 매겨진 건물이 N - 1 개의 길로 연결되어 있다. 단, 서울과학고등학교는 어떤 두 건물 사이도 연결된 길만을 이용하여 오갈 수 있다. 다음은 유효한 서울과학고등학교이다.

정후는 서울과학고등학교를 여러 조각으로 분열시킨 후 서울과학고등학교를 지배할 계획을 세우고 있다. 서울과학고등학교의 각 길은 M 개의 색 중 정확히 하나의 색으로 칠해져 있으며, 정확히 하나의 조각에 속한다. 어떤 두 길이 하나의 건물을 공유하며 같은 색으로 칠해져 있다면 두 길은 연결되어 있다. 서로 연결된 길은 같은 조각에 속하고, 연결되지 않은 길은 다른 조각에 속하도록 조각을 나눈다. 다음 서울과학고등학교는 정확히 세 개의 조각으로 쪼개진다.

정후는 서울과학고등학교에 심어놓은 스파이에게 명령하여 길에 색을 Q 번 새로 칠한다. 길을 새로 칠할 때마다 서울과학고등학교가 정확히 몇 개의 조각으로 분열하는지 정후에게 알려주자.

단, 길의 색을 새로 칠할 때, 이전에 칠해져 있던 색과 같을 수 있음에 주의하라. 새로 칠한 길은 그 길에 다시 새로운 색이 칠해지지 않는 한 지워지지 않는다.

입력

첫째 줄에 세 정수 N, M, 그리고 Q가 공백으로 구분되어 주어진다. 둘째 줄부터 N째 줄까지 N - 1 개의 줄에 세 정수 u_i, v_i, w_i가 공백으로 구분되어 주어지며, 색 w_i로 칠해진 i 번 길이 u_i 번 건물과 v_i 번 건물을 연결함을 나타낸다. N + 1째 줄부터 N + Q째 줄까지 Q 개의 줄에 두 정수 p_i, t_i가 공백으로 구분되어 주어지며, p_i번 길을 색 t_i로 색칠하라는 명령을 나타낸다.

출력

Q 개의 줄에 걸쳐, i번째 줄에는 i번째로 주어진 명령을 처리한 뒤 조각의 개수를 나타내는 하나의 정수를 출력한다.

제한

• 2 ≤ N, M ≤ 200,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ u_i < v_i ≤ N
• 1 ≤ w_i, t_i ≤ M
• i ≠ j이면 u_i ≠ u_j 또는 v_i ≠ v_j.
• 1 ≤ p_i ≤ N - 1
• 주어지는 모든 수는 정수이다.

서브태스크 1 (10점)

• 2 ≤ N, M ≤ 1,000
• 1 ≤ Q ≤ 1,000

서브태스크 2 (13점)

• 1 ≤ i ≤ N - 1일 때 u_i = i, v_i = i + 1.

서브태스크 3 (32점)

• M = 2

서브태스크 4 (45점)

추가 제한 조건이 없다.

힌트

이 문제를 풀어서 서울과학고등학교를 쪼개 버리자.