[25.03.18] ps study 백준 25515 트리 노드 합의 최댓값 (c++)

luke  · 

백준 25515 원판 돌리기

25515 문제 바로가기
문제 정리
  1. 가중치가 없는 간선을 가진 트리
  2. 각각의 노드는 정수를 소유함
  3. 루트 노드부터 방문한 노드의 값을 모두 더했을 때 최댓값 구하기(여러번 방문할 수 있고 여러번 방문해도 숫자는 한번만 더함)
풀이 전략

아이디어 트리를 루트노드부터 순회해야하니 재귀를 이용해서 푼다는 그림을 그려야한다. 한 노드에서는 자식노드들의 최댓값이 양수면 더해야 최댓값이 될 것이다. 반대로 최댓값이 양수면 더하지 않아야 최댓값이 될 것이다. 즉 루트 노드부터 dfs를 돌려 제일 자식 노드부터 양수인지 아닌 지를 판별해서 값을 더하는 문제로 바꾸어서 생각할 수 있다.

기저 판별 기저 사례는 리프노드이다. 인접 리스트에서 비어있는 인접리스트는 리프노드기 때문에 인접리스트 크기가 0인지에 대한 조건문으로 대체할 수 있다.

타입 정하기 노드의 최대 개수가 100,000개고 부여된 값의 최대는 100,000 최소는 -100,000이다. res는 최소 -100억, 최대 100억이기 때문에 long long 으로 해결가능하다.

제출한 코드
#include <bits/stdc++.h>
#define fastio cin.tie(NULL)->sync_with_stdio(0)
using namespace std;
int n, x, y;
int a[100001], vis[100001];
vector<vector<int>> v;
using ll = long long;

ll dfs(int x)
{
    if (!v[x].size())
        return a[x];

    ll res = a[x];

    for (auto next : v[x])
    {
        ll plus = dfs(next);
        if (plus > 0)
            res += plus;
    }

    return res;
}

int main()
{
    fastio;
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> x >> y;
        v[x].push_back(y);
    }
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    cout << dfs(0) << "\n";

    return 0;