제가 풀어본 문제가 아니라 잘은 모르지만, count_subtree()가 for문 안에 들어가면서 사실상 2중 for문 구조로 연산이 1억회를 넘을것으로 보입니다. 메모이제이션의 사용을 권해봅니다.
15681번 - 트리와 쿼리
제가 풀어본 문제가 아니라 잘은 모르지만, count_subtree()가 for문 안에 들어가면서 사실상 2중 for문 구조로 연산이 1억회를 넘을것으로 보입니다. 메모이제이션의 사용을 권해봅니다.
댓글을 작성하려면 로그인해야 합니다.
heewung9981 9달 전
2차원 백터로 간선 정보를 인접 리스트(같은 느낌?)으로 만든다음에
make_tree()로 단방향 그래프 처럼 만들어 subtree개수를 셀 때 부모 노트를 포함하지 않도록 만들어 줬습니다.
그 후에 count_subtree로 답을 구했는데 항상 시간초과가 납니다.
고칠점이나 잘못이해한 점이 있는지 알려주시면 감사하겠습니다.