heewung9981   9달 전

2차원 백터로 간선 정보를 인접 리스트(같은 느낌?)으로 만든다음에

make_tree()로 단방향 그래프 처럼 만들어 subtree개수를 셀 때 부모 노트를 포함하지 않도록 만들어 줬습니다. 

그 후에 count_subtree로 답을 구했는데 항상 시간초과가 납니다. 

고칠점이나 잘못이해한 점이 있는지 알려주시면 감사하겠습니다.

outsidercat   9달 전

제가 풀어본 문제가 아니라 잘은 모르지만, count_subtree()가 for문 안에 들어가면서 사실상 2중 for문 구조로 연산이 1억회를 넘을것으로 보입니다. 메모이제이션의 사용을 권해봅니다.

zenith82114   9달 전

이 구현에서는 하나의 서브트리 크기를 답하는 데 그 서브트리 크기만큼의 시간이 걸립니다. $Q$번의 쿼리가 모두 루트라면 총 $QN \le 10^{10}$의 시간이 들어 통과할 수 없습니다. 또 count_subtree의 tree도 참조자로 받으셔야 할 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.