백준 1289 (C++) 트리의 가중치

최초 업로드: 2025-09-05 03:00:43

최근 수정 시간: 2025-09-05 03:01:54

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] 트리의 가중치

[문제 링크](https://www.acmicpc.net/problem/1289)

## 문제 설명

트리는 N개의 정점과 N-1개의 간선으로 구성된 그래프이다. 트리의 성질 중 하나는 어느 두 정점 간에도 유일하게 하나의 경로가 존재한다는 것이다.

트리의 모든 간선에 음이 아닌 정수인 가중치가 배정되었다. ‘경로의 가중치’란 경로에 해당하는 간선의 곱으로 정의된다. 또한 ‘트리의 가중치’는 트리 상에 가능한 모든 경로에 대해 ‘경로의 가중치’의 합을 의미한다. 문제는 트리가 주어졌을 때 ‘트리의 가중치’를 구하는 것이다.

## 입력

첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 간선의 가중치는 W라는 것을 의미한다.

## 출력

첫째 줄에 트리의 가중치를 1,000,000,007로 나눈 나머지를 출력한다.

## 풀이
HLD에서 자주 쓰는 간선의 가중치를 정점에 매다는 테크닉을 이용하여 풀었습니다.  
누적되서 올라오는 간선의 가중치를 기록하고, 자식들끼리의 가중치 합은 누적합을 이용한 곱으로 빠르게 구했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 100'001;
const ll MOD = 1e9+7;

ll res;
bool visited[MAX];
vector<vector<pair<int, int>>> conn(MAX);

ll dfs(int cur=1, ll edgeCost=0) {
    visited[cur]=true;

vector<ll> rets;
 for(auto next : conn[cur]) {
 if(!visited[next.first]) {
 rets.push_back(dfs(next.first, next.second));
 }
 }
 int n = rets.size();
 if(!n) return edgeCost;

vector<ll> preSum(n+1);
 for(int i=0;i<n;i++) preSum[i+1] = (preSum[i] + rets[i]) % MOD;

for(int i=1;i<n;i++) res = (res+(preSum[n]-preSum[i]+MOD)*rets[i-1]) % MOD;
 res = (res+preSum[n]) % MOD;
 return (preSum[n]+1)*edgeCost % MOD;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n-1;i++) {
 int a, b, w; cin >> a >> b >> w;
 conn[a].push_back({b, w});
 conn[b].push_back({a, w});
 }
 dfs();
 cout << res;
}
```