시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 3761 | 1119 | 857 | 29.319% |
어느 날, 트리를 물끄러미 보고 있던 동현이는 엄청난 사실을 하나 발견했다. 바로 정점이 네 개인 트리는 ‘ㄷ’과 ‘ㅈ’의 두 종류밖에 없다는 사실이다!
정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자.
이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다.
신이 난 동현이는 트리만 보이면 그 트리에 있는 ‘ㄷ’과 ‘ㅈ’이 몇 개인지 세고 다니기 시작했다. 하지만 곧 정점이 $30$만 개나 있는 트리가 동현이 앞에 나타났고, 동현이는 그만 정신을 잃고 말았다. 동현이를 대신해 주어진 트리가 D-트리인지 G-트리인지 아니면 DUDUDUNGA-트리인지 알려주자!
첫 번째 줄에 트리의 정점 수 $N$이 주어진다. ($4 \leq N \leq 300\ 000$)
두 번째 줄부터 $N-1$개의 줄에 트리의 각 간선이 잇는 두 정점의 번호 $u$, $v$가 주어진다. ($1 \leq u, v \leq N$)
첫 번째 줄에 주어진 트리가 D-트리라면 D
, G-트리라면 G
, DUDUDUNGA-트리라면 DUDUDUNGA
를 출력한다.
4 1 2 2 3 3 4
D
4 1 2 1 3 1 4
G
6 1 2 2 3 3 4 4 5 4 6
DUDUDUNGA