블로그 옮겼습니다
Codeforces Round #398 (Div. 2) C. Garland
http://codeforces.com/contest/767/problem/C 이 문제는 트리가 주어지고 트리의 각각의 노드에 온도가 주어질 때 노드들의 온도의 합이 같은 세 개의 덩어리로 나누는 문제이다. 나눌수 없다면 -1을 출력 있다면 나누는 두 지점을 (답이 여러개일 경우 아무거나) 출력 하는것이다. 이 문제는 크게 세 단계로 나눌 수 있다. 1.루트 노드에서 dfs를 돌리면서 w[i] = i번 노드를 포함하는 서브트리 의 모든 노드들의 온도의 합을 구한다. 2.w[v] 가 w[root] 의 3분의 1이 되는 지점 v들을 모두 구하여 조상들에게 모두 전달해 준다.만약 노드 u 의 자식이 a,b,c 라고 했을때 a,b,c 를 각각 루트로 가지는 서브트리들에 대해 이러한 지점 v 를 가지는 자식들이 ..
Algorithm/Problem Solving
2017. 2. 19. 02:33