https://www.acmicpc.net/problem/19535
시간 2초, 메모리 1024MB

input :

• N(4 ≤ N ≤ 300,000)
• u v (1 <= u, v <= N)

output :

• D-트리 : D
• G-트리 : G
• DUDUDUNGA-트리 : DUDUDUNGA 출력

조건 :

• 정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자.

• D-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 많은 트리

• G-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 적은 트리

• DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 3배만큼 있는 트리

---

과거 데브데이(devday)에서 였는지 비슷한 문제가 있어 기록해뒀던 문제이다.

그 때에도 DFS로 풀다가 시간 초과가 발생했기에 이 문제의 풀이를 공부해 보려 하였다.
다른 풀이를 보기 전에 ㄷ, ㅈ을 구분할 때 ㅈ은 자식 노드가 2개 있다라고 생각을 했다.

실제로는 이 트리의 부모, 자식 노드를 판별할 수는 없기 때문에 차라리 degree로 체킹을 하는 것이 좋다.

다음 풀이

1. degree를 기록
2. ㄷ, ㅈ을 구성하는 degree는?

간선을 통해서 ㄷ, ㅈ을 구분할 수 있다. ㄷ 트리 중 중심을 이루는 간선을 찾은 경우 계산을 해서 구할 수 있다. ㅈ 트리는 degree가 3개 인것으로 찾을 수 있다.

직접 모든 것을 탐색하는 것보다 간선을 중심으로 확인을 할 수 있다. 간선들을 모두 체킹 하면서 ㄷ을 확인하기 위해 체크를 하고, 노드 하나씩을 돌면서 ㅈ을 확인한다.

그래서 ㄷ의 경우에는 degree의 수가 1, 2, 2, 1이기 때문에 특정 간선을 찾았을 때 (degree[u] - 1) * (degree[v] - 1)로 모든 경우를 확인할 수 있다.

ㅈ에는 degree[node]가 3 보다 큰 경우에는 선택하는 방법에 따라 ㅈ이 생성되기 때문에 조합식으로 계산을 하여 확인한다.

import sys
from collections import defaultdict


def check_g_tree(n):
    return n * (n - 1) * (n - 2) / 6


n = int(sys.stdin.readline())
edge, degree = [], defaultdict(int)
d_cnt, g_cnt = 0, 0

for _ in range(n - 1):
    u, v = map(int, sys.stdin.readline().split())
    degree[u] += 1
    degree[v] += 1
    edge.append((u, v))

for u, v in edge:
    d_cnt += (degree[u] - 1) * (degree[v] - 1)

for key in degree.keys():
    if degree[key] < 3:
        continue
    g_cnt += check_g_tree(degree[key])

if d_cnt > 3 * g_cnt:
    print("D")
elif d_cnt < 3 * g_cnt:
    print("G")
else:
    print("DUDUDUNGA")