algoshipda의 블로그

https://www.acmicpc.net/problem/1587 생각해보면 A집합 정점 갯수와 B집합 정점 갯수 둘 중 하나라도 짝수인 것이 있으면 같은 집합내에서 인접한애들끼리만 짝지어도 무조건 최대를 만들 수 있다는 것을 알 수 있다. 만약 둘 다 홀수라면 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 것 말고는 이득을 볼 것이 없다는 것을 알 수 있다. 따라서 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 간선이 있는지만 체크해서 답을 구하면 된다.

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범위를 벗어 날 수 있음에 주의한다.