테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== ㄷㄷㄷㅈ ======

===== 풀이 =====
  * 얼핏 보면 모든 노드 4개짜리 서브그래프에 대해서 ㄷ 인지 ㅈ인지를 구분해야 할 것처럼 보이지만, 이것은 매우 비효율적이다.
  * 그냥 ㄷ과 ㅈ을 각각 세어주는 편이 빠르다. 조합론적으로 O(n)에 처리할 수 있다.
  * ㄷ의 경우는, 가운데 엣지 (u,v) 를 고정시키면, (deg(u)-1)*(deg(v)-1) 로 개수를 셀 수 있고, ㅈ의 경우는 가운데 노드 u를 고정시키면 comb(deg(u),3)으로 셀 수 있다.
  * 트리 DP를 이용해도 O(n)에 구할수 있고 기여란에는 트리DP로 푼 사람도 많지만, 조합론적 방법이 구현이 훨씬 간단하다. [[https://u.acmicpc.net/9af00da7-a212-43ba-9caf-626017bf312d/ucpc20-prelim-solutions.pdf|에디토리얼]]에서 소개하는 정해도 조합론적 풀이.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 19535. ㄷㄷㄷㅈ".

- Problem link: https://www.acmicpc.net/problem/19535
- Solution link: http://www.teferi.net/ps/problems/boj/19535

Tags: [combinatorics]
"""

import sys
import math


def main():
    N = int(sys.stdin.readline())
    edges = [
        [int(x) - 1 for x in sys.stdin.readline().split()] for _ in range(N - 1)
    ]

    degs = [0] * N
    for u, v in edges:
        degs[u] += 1
        degs[v] += 1
    d_count = sum((degs[u] - 1) * (degs[v] - 1) for u, v in edges)
    g_count = sum(math.comb(deg_u, 3) for deg_u in degs)

    if d_count > g_count * 3:
        print('D')
    elif d_count < g_count * 3:
        print('G')
    else:
        print('DUDUDUNGA')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}