문제 해결/BOJ
[백준] 등산 마니아
자잘
2023. 4. 30. 23:33
https://www.acmicpc.net/problem/20188
20188번: 등산 마니아
동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오
www.acmicpc.net
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)