[백준] 24914. Split the SSHS

https://www.acmicpc.net/problem/24914

문제 요약

• 트리가 주어짐 (N = 20만)
  • 간선마다 색이 있음(M = 20만)
  • 같은색 간선이 같은 노드로 연결이 되면 같은 조각으로 침
• 쿼리가 주어짐
  • i 번 간선을 w로 칠함
  • 조각이 몇 개가 되는지 출력

접근법

• 최초 트리는 몇 조각일까?
  • 노드 기준으로 한다면?
    • 연결된 간선을 그룹으로 묶음.
    • 다른 노드도 그렇게 해봄
    • 정렬? 노드끼리 처리는?
  • 간선 기준으로 한다면?
    • 간선 양쪽노드에 같은 색이 있는지 판단
    • 둘다 같은 색이 있다면 조각은 하나 줄어듬 => 연결하니까
    • 같은 색이 하나도 없다면 조각이 하나 늘어남 => 새로운 조각이니까
    • 한쪽에라도 같은 색이 있다면 그대로 => 그 조각에 붙으니까
• 간선의 색이 바뀌면 어떻게 될까?
  • 일단 간선을 지움
    • 간선 양쪽 노드에 같은 색이 있다면 조각은 +1 => 나뉘니까
    • 같은 색이 하나도 없다면 조각은 -1 => 유일한 조각이었으니까
    • 한쪽에라도 같은 색이 있다면 변함 없음 => 조각은 계속 있을테니까
  • 간선을 추가함
    • 아까 했음
• 색이 있는지 없는지는 어떻게 판단할까?
  • 배열 -> 괜찮지만 N x M 공간 차지
  • map -> N x map 공간 차지, 전체 크기는 간선의 개수 = N - 1이니까 괜찮을것 같음
• 시간 복잡도 ${O(Q * logM)}$