[BOJ] 1289

트리의 가중치

1289번 https://www.acmicpc.net/problem/1289

하나의 예시를 들어 설명하도록 하겠습니다.

1. 루트노드인 1으로부터 시작

   acc = 1

2. 1의 첫번째 자식인 2를 조회, 1 ⇒ 2: a

   acc = 1 + a

3. 2의 첫번째 자식인 5를 조회, 2 ⇒ 5: d, 1 ⇒ 5: ad

   acc = 1 + a + ad

4. 1의 두번째 자식인 3을 조회, 1 ⇒ 3: b, 2 ⇒ 3: ab, 5 ⇒ 3: adb

   acc = 1 + a + ad + b

5. 1의 세번째 자식인 4를 조회, 1 ⇒ 4: c, 2 ⇒ 4: ac, 5 ⇒ 4: adc, 3 ⇒ 4: bc

   acc = 1 + a + ad + b + c

즉, dfs를 돌되, cur을 조회할 때 acc × (부모 ⇒ cur) 을 결과값에 더해주고 acc에 (root ⇒ cur)을 더해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1289.cpp