[백준] 31795. V.I.P.

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

문제요약

• 그래프가 주어짐(N 10^5, M 10^5)
• 노드마다 가중치가 있음(10^9)
• 활성화된 간선이 있음(u,v)
• VIP : 활성화된 간선을 이용해서 정점의 가중치가 증가하는 방향으로 이루어진 경로
• 쿼리가 주어짐(Q 10^5), (u,v)를 활성<->비활성으로 바꾸고, VIP 개수를 구하고, 다시 원복

접근법 - step 1

• 일단 쿼리를 생각하지 말고 VIP 개수를 구해본다
• 특정 노드에서 끝나는 VIP 개수
  • 연결된 노드에서 온다고 생각
  • 단 연결된 노드의 가중치는 특정 노드의 가중치보다 작아야함
  • 연결된 노드 중 가중치가 작은 노드들로 끝나는 VIP 개수들의 합
  • ${f(u) = \sum(f(v)), v: u-v는 활성화, 가중치(v)<가중치(u)}$
• 같은 요령으로 특정 노드에서 시작하는 VIP의 개수를 구할 수 있음
• 이렇게 구한 VIP 개수를 모두 합한 것이 전체 VIP의 개수

접근법 - step 2

• 이제 쿼리를 처리해본다.
• (u,v)를 활성/비활성으로 변경할때마다 VIP 개수를 구한다.
• 가중치(u) = 가중치(v) 인 경우는 경로 개수에 영향을 주지 않음
• 편의상 가중치(u) < 가중치(v)로 생각
• 비활성 -> 활성인 경우
  • 기존 경로에서 u -> v 경로가 생김
  • (u로 끝나는 VIP 개수) x (v로 시작하는 VIP 개수) 만큼 전체 VIP 개수가 늘어날 것임
• 활성 -> 비활성인 경우
  • u -> v 경로가 삭제됨
  • (u로 끝나는 VIP 개수) x (v로 시작하는 VIP 개수) 만큼 전체 VIP 개수가 줄어들 것임