BOJ 7812 - 중앙트리
INC 2007 H번
https://www.acmicpc.net/problem/7812
루트를 하나 잡고 DFS를 통해 루트에서 다른 모든 정점으로 가는 비용의 합을 구해 놓는다. 이 때 정점 u(1 ~ n)를 루트로 하는 서브트리의 정점 갯수도 구해 놓는다. 다시 DFS를 돌리는데 이때 처음에 루트에서 아까 구한 비용의 합을 들고 시작하면서 최소답을 갱신시켜 나간다.
cost(u, v) = 간선(u, v)의 비용
count(u) = u를 루트로 하는 서브트리의 정점의 갯수
라 하자. 간선(u, v)를 탈때 cost(u, v) * count(v) 만큼 답이 줄어들고 cost(u, v) * (n - count(v)) 만큼 답이 늘어나는걸 이용하면 된다. 시간 복잡도는 O(N). 답이 int범위를 벗어 날 수 있음에 주의한다.
https://www.acmicpc.net/problem/7812
루트를 하나 잡고 DFS를 통해 루트에서 다른 모든 정점으로 가는 비용의 합을 구해 놓는다. 이 때 정점 u(1 ~ n)를 루트로 하는 서브트리의 정점 갯수도 구해 놓는다. 다시 DFS를 돌리는데 이때 처음에 루트에서 아까 구한 비용의 합을 들고 시작하면서 최소답을 갱신시켜 나간다.
cost(u, v) = 간선(u, v)의 비용
count(u) = u를 루트로 하는 서브트리의 정점의 갯수
라 하자. 간선(u, v)를 탈때 cost(u, v) * count(v) 만큼 답이 줄어들고 cost(u, v) * (n - count(v)) 만큼 답이 늘어나는걸 이용하면 된다. 시간 복잡도는 O(N). 답이 int범위를 벗어 날 수 있음에 주의한다.
이 문제 때문에 한동안 씨름하고 있었는데 정말 감사합니다
답글삭제