[백준] 1289: 트리의 가중치 (Java, Python)
트리의 가중치백준 1289 트리 DP Python Java문제 분석트리: N개 정점, N-1개 간선 (가중치 있음)경로의 가중치: 경로 상 간선 가중치의 곱트리의 가중치: 모든 정점 쌍 (u, v) 간 경로 가중치의 합제약: N ≤ 100,000 / W ≤ 1,000 / 답은 mod 109+7핵심: 합이 아니라 곱이므로 "각 간선 기여도" 기법은 사용 불가 → 트리 DP 필요접근법트리 DP — O(N)트리를 루팅한 뒤, 각 정점 v에서:dp[v] = v에서 서브트리 내 모든 후손까지 경로 가중치(곱)의 합h[c] = wc × (1 + dp[c]) — v에서 자식 c의 서브트리 전체로 가는 경로 가중치 합정점 v의 기여:v → 후손 경로: Σ h[ci]서로 다른 서브트리를 잇는 경로 (v가 LCA): Σi..
Problem Solving/Baekjoon
2026. 2. 16. 14:39
