개요
문제가 있는 링크
골드 4, DFS, DP
자식노드 검색시 루트노드가 추가한 특정 값의 합의 최대값
입장
- 제가 DP를 잘 못해서 DFS나 재귀함수로 해결했습니다. 먼저 총계는 10^10이므로 long long을 사용합니다.
- 자식 노드가 없으면 현재 위치의 특정 값을 반환합니다. 자식 노드가 있으면 어떻게 됩니까? 자식 노드의 DFS가 0보다 크면 추가됩니다. 구현은 C++의 광기 벡터를 사용합니다.
- 메모이제이션을 사용해 보았지만 성능에는 큰 차이가 없었습니다. 그 이유는 한 번 방문한 노드는 다시 방문하지 않기 때문입니다.
의사 코드
DFS(cur) {
if (child(cur).length == 0)
return value(cur)
for (c = child)
if (0 < DFS(c))
ret += DFS(c)
return ret
}소스 코드
#include <iostream>
#include <vector>
using namespace std;
#define N 100010
using ld = long long;
typedef vector<int> vec;
vec tree(N);
ld a(N);
ld dfs(int u) {
if (!tree(u).size()) return a(u);
ld v=a(u), t;
for (auto c:tree(u)) {
t = dfs(c);
if (0<t) v += t;
}
return v;
}
int main() {
int n;
cin >> n;
int u,v;
for (int i=0; i<n-1; i++) {
cin>>u>>v;
tree(u).push_back(v);
}
for (int i=0; i<n; i++)
cin >> a(i);
cout << dfs(0);
}