[python] 20188 등산 마니아

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

 

 

 

 

 

문제 해결

트리와 DFS를 사용해야한다는 것은 쉽게 알 수 있지만 어떻게 활용할지 매우 어려운 문제

https://youtu.be/AQzKDzQqIRE

다음 동영상을 봐도 어렵다...

 

 

CODE

import sys
input = sys.stdin.readline
from collections import deque, defaultdict
sys.setrecursionlimit(10**8)


def dfs(cur, parent):
    global ans

    for child in graph[cur]:
        if child != parent:
            dfs(child, cur)
            dp[cur] += dp[child] + 1

    val = (dp[cur] + 1) * (n - dp[cur] - 1) + (dp[cur]*(dp[cur] + 1)//2)

    if cur != 1:
        ans += val

if __name__ == "__main__":
    n = int(input())

    dp = [0]*(n+1)
    graph = defaultdict(list)

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