트리1068

스태틱 변수 만들고 로컬변수 이름 같은거 사용하는줄도 모르고 시간 날렸네 하...

구현은 어렵지 않았는데 삭제할때 경우에 따라 처리하는 부분
리프노드 파악할때도 경우에 따라 처리하는 부분
들 때문에 예외처리하느라 오래걸렸다

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

import java.io.*;
import java.util.*;

public class Main
{
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();

    static int[] leafCount;

    static int rootId;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; ++i)
            tree.add(new ArrayList<>());

        rootId = 0;
        int[] arrP = new int[N];

        String[] input = br.readLine().split(" ");
        for(int i = 0; i < N; ++i)
        {
            int C = i;
            int P = Integer.parseInt(input[i]);

            if(P == -1)
            {
                rootId = C;
                continue;
            }

            tree.get(P).add(C);
            tree.get(C).add(P);
            arrP[i] = P;
        }

        leafCount = new int[N];

        recur_makeCount(-1, rootId);

        int delId = Integer.parseInt(br.readLine());

        if(delId == rootId)
        {
            System.out.println(0);
            return;
        }

        ArrayList<Integer> PofDel = tree.get(arrP[delId]);
        if(arrP[delId] == rootId)
        {
            if(1 < PofDel.size())//부모가 루트이고 자식 2개
                System.out.println(leafCount[rootId] - leafCount[delId]);
            else
                System.out.println(1);
        }
        else
        {
            if(2 < PofDel.size())//부모가 자식 2개 (1개는 부모의 부모)
                System.out.println(leafCount[rootId] - leafCount[delId]);
            else
                System.out.println(leafCount[rootId] - leafCount[delId] + 1);
        }

    }

    public static int recur_makeCount(int parent, int nodeId)
    {
        ArrayList<Integer> curNode = tree.get(nodeId);

        if(nodeId == rootId )
        {
            if(curNode.isEmpty() == true)
                leafCount[nodeId] = 1;
        }
        else
        {
            if(curNode.size() == 1)
                leafCount[nodeId] = 1;
        }


        for(int child : curNode)
        {
            if(child == parent)
                continue;
            leafCount[nodeId] += recur_makeCount( nodeId, child);
        }

        return leafCount[nodeId];
    }
}

반례모음

2
-1 0
1
ans: 1

12
-1 0 0 2 2 2 4 3 3 8 8 8
4

ans: 6

1
-1
0

ans:0

9
1 6 4 1 3 3 8 8 -1
3

ans: 2


4
-1 0 1 2
2

ans: 1

7
3 6 6 -1 0 6 3
4

ans: 4


2
-1 0
1

ans: 1