[백준] 31839. 불꽃놀이의 아름다움

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

문제 요약

• N개의 노드를 갖는 트리가 주어짐 (N : 20만)
• 각각의 노드는 가중치 ${W_i}$를 갖고 있음
• 특정 노드를 기준으로 정할때, sum(각 노드까지의 최단 거리 x ${W_i}$) 을 최대로 하는 값 구하기

접근법

• 물론 모든 노드에 대해서 값을 계산하면 좋겠지만 O(n^2)
• 하나를 계산하고 근처 노드로 이동하는 경우를 생각해보면 "변화하는 양"을 계산 가능하다.
• 문제의 예시를 보면
  • 2 3
  • 3 1
  • 4 1
  • 1 5
• 1번 노드를 루트로 하는 트리를 생각해 볼 수 있다.
• 1,2,3,4,5의 가중치를 a,b,c,d,e로 표현하면
• 1번 노드가 기준일때의 각 노드까지의 거리는 : 2b + c + d + e
  • 2번노드 : 2
  • 3번노드 : 1
  • 4번노드 : 1
  • 5번노드 : 1
• 이때 1번노드에서 3번노드로 이동하는 경우 : a + b + 2d + 2e
  • 1번노드 : 1
  • 2번노드 : 1
  • 4번노드 : 2
  • 5번노드 : 2
• 이동할때 특징이 3번노드쪽에 있는 노드와는 가까워지고, 3번노드의 다른쪽에 있는 노드와는 멀어지는 특징이 있다.
• 그 특징은 값의 변화에 반영이 되는데
  • (2b + c + d + e) -> (a + b + 2d + 2e)
  • +a, -b, -c, +d, +e
  • 즉 3번 노드의 하위인 2번 3번 노드는 감소하고
  • 그 외의 노드인 1,4,5 노드는 증가함
• 이 특징을 이용해서 해결이 가능함
  • 특정 노드(1번노드)를 루트로 하는 트리를 구성하고
  • 각각의 노드들의 자식 노드들의 합을 미리 구해놓음
  • 동시에 1번 노드가 기준점일때의 값도 구해놓음
  • 이후 1번에서 근처 노드로 움직일때 값의 변화를 반영함
    • 이동한 쪽의 자식 노드들의 합만큼 감소
    • 그 외의 노드들의 합만큼 증가 : 그 외의 노드들의 합은 전체 합 - 이동한쪽 자식노드들의 합