상사 없 는 무도회 (트 리 DP) 문제 풀이

제목 전송 문
제목 설명
우랄 대 는 직원 N 명 으로 1 ∼ N 번 호 를 매 겼 다.
그들의 관 계 는 마치 교장 을 뿌리 로 하 는 나무 와 같 고 아버지 노드 는 바로 자식 노드 의 직접적인 상사 이다.
각 직원 은 하나의 즐거움 지 수 를 가지 고 있 으 며, 정수 HiHi 로 제시 하 며, 그 중 1 ≤ i ≤ N.
지금 은 주년 축하 파 티 를 열 려 고 하지만 직접 상사 와 함께 참석 하고 싶 어 하 는 직원 은 없다.
이 조건 을 만족 시 키 는 전제 에서 주최 측은 일부 직원 을 초청 하여 모든 참석 직원 들 의 즐거움 지 수 를 합 쳐 이 최대 치 를 구 하 기 를 희망 한다.
입력 형식
첫 줄 의 정수 N.
이 어 N 행, i 행 은 i 번 직원 의 쾌락 지수 Hi 를 나타 낸다.
다음 N - 1 줄 에 한 쌍 의 정수 L, K 를 입력 하면 K 는 L 의 직접적인 상사 임 을 나타 낸다.
마지막 줄 에 0, 0 을 입력 하 세 요.
출력 형식
수출 최대 즐거움 지수.
데이터 범위
1≤N≤6000 −128≤Hi≤127
입력 예시:
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
출력 예시:
5
트 리 DP:
트 리 나 그림 에 있 는 DP 입 니 다. 보통 부모 노드 나 하위 노드 가 특별한 요구 가 있 을 때 사용 하 는 DP 입 니 다.
먼저 그림 을 만 들 고 그림 을 옮 겨 다 닐 때 DP 작업 을 합 니 다. 이 문제 에 있어 우 리 는 F (i, j) 로 i 라 는 노드 를 표시 합 니 다. 상 태 는 j (0 으로 선택 하지 않 음 을 표시 하고 1 로 선택) 값 의 최대 치 입 니 다. 각 노드 에 대해 우 리 는 두 가지 조작 이 있 습 니 다.
1. 현재 이 노드 를 선택 하 십시오. j 상 태 는 1 입 니 다. 하위 노드 는 선택 하지 않 을 수 밖 에 없 기 때문에 f (i, 1) = f (i, 1) + f (u, 0) (u 는 i 의 하위 노드 를 표시 합 니 다)
2. 현재 이 노드 를 선택 하지 않 습 니 다. j 의 상 태 는 0 입 니 다. 그의 하위 노드 는 선택 할 수도 있 고 선택 하지 않 아 도 됩 니 다. 두 사람의 최대 치 를 가 져 옵 니 다.
그래서 f (i, 0) = f (i, 0) + max (f (u, 1), f (u, 0) (u 는 i 의 하위 노드 를 나타 낸다)
3. 임의의 노드 부터 검색 하기 때문에 부모 노드 가 있 는 노드 를 저장 하 는 배열 이 필요 합 니 다.

#include
#include
using namespace std;
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;//     
int f[N][2];
bool vis[N];
void add(int a, int b)//   
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int cur)//  ，  DP
{
    f[cur][1] = happy[cur];
    for(int i = h[cur]; i != -1; i = ne[i]){//     
        int j = e[i];
        dfs(j);
        f[cur][0] += max(f[j][0], f[j][1]);
        f[cur][1] += f[j][0];
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> happy[i];//  
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        vis[a] = true; //  a     
        add(b, a);
    }
    
    int root = 1;
    while(vis[root])root++;///       
    
    dfs(root);
    cout << max(f[root][0], f[root][1]);
    return 0;
}