양갈래 구하기 (백준 31477)

안녕하세요. 오늘은 끊을거예요.

문제

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

아이디어

DFS(node)를 node를 루트로하는 서브트리에서의 모든 리프노드가 node와 닿지 않게하는 최소의 비용이라고 정의합시다.
DFS(node)는 모든 자식들 next에 대해서 node-next 잇는 간선의 비용과 DFS(next)의 최솟값의 누적합이 정답이 됩니다.
만약 node가 리프노드이면 최댓값, 1e9를 반환해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector <pair <ll, ll> > v[101010];
ll DFS(ll node, ll before)
{
    ll ans = 0;
    for (auto next : v[node])
    {
        if (next.first == before) continue;
        ans += min(next.second, DFS(next.first, node));
    }
    if (ans == 0) ans = 1e9; //만약 맨 끝이라면 (리프노드라면) 최댓값 반환
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, a, b, c;
    cin >> N;
    for (i = 1; i <= N - 1; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }

    cout << DFS(1, 0);
}

감사합니다.