[백준] 등산 마니아

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

20188번: 등산 마니아

import sys, math
from collections import deque, defaultdict

sys.setrecursionlimit(10 ** 8)

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

dp = [0] * (n + 1)

graph = defaultdict(list)

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

ans = 0


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


dfs(1, 0)

print(ans)