[c++] 백준 25515 트리 노드 합의 최댓값

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

25515번: 트리 노드 합의 최댓값

tree dp를 통해 해결하는 문제이다.

 

만약 현재 정점의 비용을 cur_cost, 다음 정점의 비용을 next_cost라 하면

현재 정점에서의 최댓값은 다음이 성립함을 알 수 있다.

cur_cost = max(cur_cost+next_cost, cur_cost)

(비용이 음수 일 수도 있기 때문에 최대를 선택해주어야 한다)

#include<bits/stdc++.h>
using namespace std;
#define N 100100
typedef long long ll;
vector<int> tree[N];
ll dp[N],weight[N],n;
bool visited[N];
void dfs(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    dp[cur] = weight[cur];
    for(auto next : tree[cur]){
        if(visited[next])
            continue;
        dfs(next);
        dp[cur] = max(dp[cur]+dp[next],dp[cur]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<n; i++){
        int a,b; cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    for(int i=0; i<n; i++)
        cin>>weight[i];
    dfs(0);
    cout << dp[0];
    return 0;
}