UCPC 2020 예선 D / ㄷㄷㄷㅈ - 19535

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N;
    cin >> N;
    vector<vector<int>> adj(N+1);
    int u, v;
    for(int i =0; i<N-1; ++i) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    long long D= 0, G = 0;
    for(int i = 1; i<=N; ++i) {
        long long size = adj[i].size();
        G += size*(size-1)*(size-2)/6;
        for(int j = 0; j<size; ++j) {
            int there = adj[i][j];
            if(i > there) continue;
            D += (size-1)*(adj[there].size() - 1);
        }
    }
    if(D > 3*G) cout << "D";
    else if(D < 3*G) cout << "G";
    else cout << "DUDUDUNGA";    
}

 

 

 

 

 

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

19535번: ㄷㄷㄷㅈ

 

 

 

 

 

ㄷㄷㄷㅈ

두 모양의 성질을 이용해 해결 할 수 있습니다.

우선 G-트리의 개수는, 각각의 정점에 인접한 정점 중 3개를 뽑는 경우의 수를 모두 더한것과 같습니다.

D-트리의 개수는, 한 간선을 공유하는 두 정점에서, 각각 정점의 인접한 정점의 수를 곱한것을 모두 도한것과 같습니다.