[BOJ-1068]트리

노드의 수(N~[1,50])가 주어지고, 각 노드의 부모를 입력으로 주었을 때

k 노드를 지웠을 때 leaf 노드의 수를 구하는 문제 단순구현?

N이 크지 않아서 지울 노드의 서브트리를 순회하면서 각 노드의 값을 -1 로 바꾸고, 그 중 자식수가 0인 것만 값을 출력으로 했음.

하나 생각하지 않았던 게 

트리가 편향트리? 한쪽으로만 길게 

0 < 1 < 2 < 3 이런 식으로 이어진 노드였다면 

부모<<<자식

1을 지우면 0만 남게 되어서 답이 1을 출력해야하는데, 내가 처음 작성한 코드는 부모와 관련이 1도 없는 걸로 작성했음... 그래서 WA 뭐 70% 까지는 맞았는데 test data 부족해서 맞았으면 아~ 이렇게 하면되는구나 넘어갈뻔 제출할 때 의심1도안해서 .........................................;;;;;;; 제출하고 잘못했구나 생각..........

#include<cstdio>
#include<vector>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
VVI T; // Tree
VI CN; // 1-vector CN ; The # of child of parent node 
VI P; // 1-vector P ; child node of Parent
 
void traversal(int del){
    for(auto iter = T[del].begin() ; iter != T[del].end() ; iter++){
        int node = *iter;
        CN[node] = -1;
        traversal(node);
    }
    return ;
}
int main(){
    int n;
    scanf("%d", &n);
    // 0 ~ n-1 ; n~[1,50]
    T = VVI(n);
    CN = VI(n);
    P = VI(n);
    for(int child = 0  ; child < n ; child++){
        int parent;
        scanf("%d", &parent); 
        if(parent!=-1){
            CN[parent]++; // parent node ; # of children node 
            T[parent].push_back(child);
            P[child] = parent; // WA1 ; add src
        }        
    }
    int del; scanf("%d", &del);
 
    CN[del] = -1;
    if(P[del] != -1) CN[P[del]]--; // WA1 ; add src
    traversal(del);
 
    int ans = 0;
    for(int i = 0 ; i < n ; i++) if(CN[i]==0) ans++;
 
    printf("%d",ans);
    return 0;
}
// 68? 70? WA
 
//4
//-1 0 1 2
//1
// 옳은 값 1 WA 0