[BOJ/백준][Gold3] 19535 : ㄷㄷㄷㅈ (C++)

https://www.acmicpc.net/problem/19535

19535번: ㄷㄷㄷㅈ

 

 

[난이도] Gold3
[유형] 트리

[풀이]
각 노드가 몇개의 인접한 노드를 가지고 있는지와 N-1개의 간선 (u,v) 만
저장해주면 문제를 풀 수 있습니다.
acnt[300001] 배열을 선언하여 acnt[i] : i번 노드와 연결된 노드 개수로 정의한 뒤 값을 저장해주었습니다.

D-트리의 개수 : 모든 간선 N-1개의 (u,v) 에 대해 (acnt[u]-1) * (acnt[v]-1) 의 값을 더해주면 됩니다.
                u와 연결된 u`, v와 연결된 v`을 이용해 [u` - u - v - v`] 형태의 D 트리를 만들 수 있습니다.
                1을 빼주는 이유는 [u-v] 간선을 빼주는 것입니다.

G-트리의 개수 : 1~N번 노드 i에 대해 조합 acnt[i]C3 을 구해주면 됩니다.
                acnt[i] 중 3개를 뽑으면 i 중심으로 3개의 간선이 연결된 트리가 되기 때문입니다.

 

#include <cstdio>
#include <vector>
using namespace std;
int N;
int acnt[300001];
vector<pair<int,int>> p;
int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        acnt[u]++, acnt[v]++;
        p.push_back({u,v});
    }
    long long a=0,b=0;
    for(auto [u,v] : p) a+=(acnt[u]-1)*(acnt[v]-1);
    for(int i=1;i<=N;i++) if(acnt[i]>=3) b+=(acnt[i]*(acnt[i]-1)*(acnt[i]-2))/6;
    b*=3;
    if(a>b) puts("D");
    else if(a<b) puts("G");
    else puts("DUDUDUNGA");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/19535.cpp