블로그 옮겼습니다

http://codeforces.com/contest/681/problem/D 간단하게 문제를 설명하자면, N개의 사람이있고 M개의 연결관계가 주어진다그리고 하나의 컴포넌트는 트리구조를 이룬다. (여러개의 컴포넌트로 이루어질 수도 있음)N명의 사람들 각각은 선물을 주고 싶은 사람이 한사람 씩 있는데 이 한 사람은 무조건 자기 자신이거나 자신의 조상이어야 한다. 또, 우리는 어떤 list를 작성해야하는데각 N명의 사람들은 list의 맨왼쪽에 있는 명단부터 차례대로 봐가면서 무조건 가장 처음으로 등장하는 조상에게 선물을 줘야한다. 그리고 만약 list를 끝까지 다 봤는데도 자신의 조상이 나오지 않는다면 아무에게도 선물을 주지 못하고 집에간다. 문제는 N명의 사람모두가 자기가 선물을 주고 싶은 사람에게 선물을..

그래프 + dp 이다. N

사실 원래의 풀이와 아주 큰 차이는 없다. 두번의 dfs를 돌리는 것까지는 똑같지만 변수가 하나 줄었고, 점화식이 좀 더 단순해 졌다. 우선 size(i) 는 i를 루트로 갖는 서브트리의 총 노드수라고 보면노드 i 부터 자손들까지의 거리의 총합 S(i)는,노드 i의 자식이 c1, c2, c3..... cn 이고, ck 와 연결된 간선의 가중치는 wk 일때size(c1)*w1 + size(c2)*w2 +....+size(cn)*wn +S(c1) + S(c2) + S(c3) +.....+S(cn) 이다.즉 각각의 간선에 대해 몇번 지남당하는지를 계산한다고 보면된다. 이렇게 각각의 간선에 대해 몇 개의 경로에 대해 지남 당하느냐로거리 의 총합을 구하는 경우가 많은 것같다. 트리상에 존재하는 모든 정점쌍간의 거..