[Python] 23835 - 어떤 우유의 배달목록(Easy)

n = int(input())

graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

q = int(input())

answer = [0] * n


def dfs(node, end, cnt=0):
    if node == end:
        answer[end] += cnt
        return cnt
    visit[node] = True
    for next in graph[node]:

        if not visit[next]:
            if dfs(next, end, cnt + 1):
                answer[node] += cnt
                return cnt

    return 0


for i in range(q):
    query = list(map(int, input().split()))
    visit = [False] * n

    if query[0] == 1:
        start, end = query[1] - 1, query[2] - 1
        dfs(start, end)
    else:
        print(answer[query[1] - 1])

간단한 DFS 문제

쿼리문이 1일 경우 start에서 end 까지 dfs를 돌리면서 최종 end까지 배달하면서 놓는 우유를 answer[] 배열을 정의해서 더해준다 .

시간복잡도는 대략 O(NQ) = 1000 1000인 백만으로 충분히 통과한다.

이보다 어려운버전인 Hard버전은 N과 Q가 10만이던데 그건 어떻게 푸는지 감도 안온다