백준: 20171

</br> 2020 본선 중 골드 문제 풀기
</br>

20171: Dessert Café

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

트리가 있고, 노드들 중 아파트 단지가 있다
각 노드들에서 아파트 단지까지의 거리를 다 잰다.
만약 a 노드에서 다른 단지까지의 거리들이 b 노드에서 모든 다른 단지까지의 거리들보다 더 멀다면, a는 bad place다.
good place들의 개수 세기

#include <bits/stdc++.h>

using namespace std;

vector<int> tree[100001];
int aparts[100001];
int nums[100001];
int ans = 0;

int func(int root, int now, int pre){
    int ret = 0;
    if( aparts[now] ) ret++;
    for(int i = 0; i < tree[now].size(); i++){
        int nx = tree[now][i];
        if( nx == pre ) continue;
        ret += func(root, nx, now);
    }
    nums[now] = ret;
    return ret;
}

void func2(int root, int now, int pre){
    if( nums[now] == 0 ) return;

    int cnt = 0;
    for(int i = 0; i < tree[now].size(); i++){
        int nx = tree[now][i];
        if( nx == pre ) continue;
        if( nums[nx] ) cnt++;
        func2(root, nx, now);
    }
    if( cnt >= 2 ) ans++;
    else if( cnt == 1 && nums[root] > nums[now] ) ans++;
    else if( aparts[now] ) ans++;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    for(int i = 0; i < n-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    for(int i = 0; i < k; i++){
        int a;
        cin >> a;
        aparts[a] = 1;
    }

    func(1, 1, 0);
    func2(1, 1, 0);

    cout << ans << endl;

}

우선 아파트 단지 자체는 good place인 게 당연하다.
주어진 예제를 보니, 1, 3, 7만 bad place다. 아 그럼 리프 노드인가? 싶은데 그럼 너무 쉬울 거고
그래서 계속 보니까 현재 노드가 중간점이 된다. 즉 내 양 편에 아파트 단지가 있으면 good place가 된다

위 그림처럼
그럼 결국 노드 간의 거리는 의미가 없네ㅋㅋ

처음엔 노드 하나 하나 아파트 단지가 두 쪽 이상에 있는 지 검사했는데, 시간 초과 났다

그래서 일단 1번을 루트로 보고 노드 마다 자식들의 아파트 단지 수를 다 메모해 놓았다.

그럼 이렇게 된다.
여기서 만약 현재 단지 수가 0이면 자신이 중간점이 되지 못하므로 bad place다.
그리고, 단지 수가 0이 아닌 자식들이 2개 이상이면 그들 사이의 중간점이 되므로 good place다.
단지 수가 0이 아닌 자식들이 1개라면, 부모 쪽에 아파트 단지가 있다면 good place가 될 수 있고, 아니면 bad place다.
</br>

---

어렵다… 어려워 한참 틀렸다
</br>