트리를 간단하게 색칠하는 최소 비용 (백준 25512)

안녕하세요. 오늘은 트리를 간단하게 색칠할 거예요.

문제

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

아이디어

0번 노드의 색깔만 확정되면 나머지는 자동으로 확정이 됩니다.
그러므로 0번노드가 black일때, white일때를 나누어주면 됩니다.

0번 노드의 dpt값이 0이라고 하면 dpt%2값이 같은 노드끼리는 색깔이 같습니다. 그래서 cnt[0]과 cnt[1]에 두가지 경우를 나누어주면 됩니다.

소스코드

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

ll ans[2] = { 0 }, cost[101010][2] = { 0 };
vector <ll> v[101010];
void DFS(ll node, ll up, ll dpt)
{
    ans[0] += cost[node][dpt % 2];
    ans[1] += cost[node][(dpt + 1) % 2];
    for (ll next : v[node])
        if (next != up)
            DFS(next, node, dpt + 1);
}

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

    DFS(0, -1, 0);
    cout << min(ans[0], ans[1]);
}

감사합니다.