흙금이네 블로그

아이디어 루트 노드에서 시작한 DFS로 리프 노드에서부터 서브 트리에 속한 노드 개수를 구해 나간다. 풀이 #1 간선 정보를 2차원 리스트 graph에 저장하고, 서브 트리의 노드 개수를 저장하는 N+1 길이의 리스트 dp를 만든다. 함수 dfs에서 현재 노드의 서브 트리에 속한 노드 개수를 저장하는 cnt를 현재 노드를 고려하여 1로 초기화한다. for문에서 자식 노드들의 간선 정보에 포함된 현재 노드를 지우고, 자식 노드들의 반환값을 cnt에 더한다. 자식 노드들의 반환값을 모두 더한 cnt를 현재 노드 번호를 인덱스로 dp에 저장한 후 반환한다. 리프 노드에서는 for문이 실행되지 않고 처음 저장된 1이 그대로 반환된다. 루트 노드을 인자로 함수 dfs를 호출한 후, 쿼리에 따라 서브 트리의 노드 ..