[백준] 13896. Sky Tax

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

문제 요약

• 트리의 루트가 바뀌고
• 특정 노드의 자식 개수를 카운팅

접근법

• 트리를 1번 노드를 루트로 정하고 고정시킴
• 새로운 루트(r)와 특정 노드(a)의 관계를 관찰하다가 정리하면
  • r이 a의 자식인 경우 : r이 루트가 되면 a의 자식 중 일부는 여전히 a의 자식이지만, 일부는 아니게 될 것임
    • 아니게 될 자식의 개수를 어떻게 찾을것인가?? ==> 주요 관심사
  • 그렇지 않은 경우 : r이 루트인 트리에서도 a의 자식은 그대로 유지될 것임
• ETT(오일러투어테크닉)을 이용해서 자식인지는 판단가능
• "주요관심사"를 해결하기 위해서 a와 직접 연결된 노드들을 관찰해보면
  • 각각을 서브트리라고 볼때
  • r이 포함되는 서브트리의 크기가 "주요관심사"임
    • 왜냐면 그들은 a를 거치지 않고도 r에 도달할 수 있음
  • ett의 특성에 따라 r이 포함되는 서브트리를 적절한 방법으로 찾을 수 있음
    • 서브트리의 루트를 알기때문에 r이 포함되는지 일일이 비교해가면서 찾아볼 수도 있지만
    • 범위는 다음 서브트리의 루트 전까지 일 것이므로 이를 응용해서 upper_bound를 사용했음