출처 : https://www.acmicpc.net/problem/20188 풀이 방법완전 탐색으로 노드를 기준으로 하면 시간 복잡도가 N^2 이므로 시간 초과된다.시간 복잡도를 줄이기 위해 DP를 사용할까 했지만, 노드를 기준으로 문제를 완벽하게 분리하는 것이 쉽지 않았다.이럴 때 필요한 것이 역발상 즉 간선을 기준으로 생각해 보면 정답을 구할 수 있다. 위 그림에서 5-6을 잇는 간선을 지나가는 경우는 5를 루트로 하는 서브트리의 노드 중 2개를 선택하거나, 5의 서브트리 노드 중 하나를 선택하고, 1, 4, 3중에 하나를 선택하는 경우라고 알 수 있다.그러므로, 각 노드를 루트로 가지는 서브트리에서 노드의 수를 계산해 주면 된다. 이는 dfs로 계산하고, 나온 값이 ret라고 하면, ret * (r..
