[LA 6745 Traitor] 트리에 DP 덮어쓰기

제목.
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=607&page=show_problem&problem=4757
분석하다.
클래식 트리에 DP 덮어쓰기
f[i][0]를 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에게 덮이지 않고 아들의 최대치도 덮지 않는다.
f[i][1]을 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에게 덮이지만 아들의 최대치를 덮지 않는다.
f[i][2]를 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에게 덮어씌우지 않지만 아들의 최대치를 덮어씌운다.
f[i][3]를 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에 의해 덮이고 아들의 최대치도 덮는다.
그러면
f[i][0]=sigma {f[j][0], f[j][1], f[j][2], f[j][3]}, j는 i의 아들
f[i][1]=max {sigma {f[j][0], f[j][1], f[j][2], f[j][3]}} +max {f[k][0], f[k][1]} +tag[i]}, k는 i의 어떤 아들이고 j는 i가 k를 제외한 아들이다.
f[i][2]=max {sigma {f[j][0], f[j][1], f[j][2], f[j][3]}} +max {f[k][0], f[k][2]} +tag[k]}, k는 i의 어떤 아들이고 j는 i가 k를 제외한 아들이다.
f[i][3]=max {sigma {f[j][0], f[j][1], f[j][2], f[j][3]}}}+max {f[p][0], f[p][1]}+tag[i]+max {f[q][0], f[q][2]}+tag[q]}, p와 q는 i의 어떤 아들이고 j는 p와 q를 제외한 아들이다.
3 전송의 경우 DP 1개로 수행
시간 복잡도 O (N)
코드

/**************************************************
 *        Problem:  LA 6745
 *         Author:  clavichord93
 *          State:  Accepted
 **************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAX_N = 10005;
const int MAX_E = 10005;

struct Edge {
    int dest;
    Edge *next;
    Edge() {}
    Edge(int _dest, Edge *_next) : dest(_dest), next(_next) {}
};

Edge EdgePool[MAX_E];
Edge *EP;
Edge *e[MAX_N];

int n, m;
int parent[MAX_N];
int tag[MAX_N];

int f[MAX_N][4];
int g[MAX_N];
int h[4];

inline void addedge(int a, int b) {
    e[a] = new(EP++)Edge(b, e[a]);
}

void dp(int i) {
    for (Edge *j = e[i]; j; j = j->next) {
        dp(j->dest);
    }
    int sum = 0;
    for (Edge *j = e[i]; j; j = j->next) {
        sum += g[j->dest];
    }
    f[i][0] = sum;
    f[i][1] = f[i][2] = f[i][3] = 0;
    h[0] = h[1] = h[2] = h[3] = 0;
    for (Edge *j = e[i]; j; j = j->next) {
        f[i][1] = max(f[i][1], sum - g[j->dest] + max(f[j->dest][0], f[j->dest][1]) + tag[i]);
        f[i][2] = max(f[i][2], sum - g[j->dest] + max(f[j->dest][0], f[j->dest][2]) + tag[j->dest]);
        h[3] += g[j->dest];
        h[3] = max(h[3], h[2] + max(f[j->dest][0], f[j->dest][1]) + tag[i]);
        h[3] = max(h[3], h[1] + max(f[j->dest][0], f[j->dest][2]) + tag[j->dest]);
        h[2] += g[j->dest];
        h[2] = max(h[2], h[0] + max(f[j->dest][0], f[j->dest][2]) + tag[j->dest]);
        h[1] += g[j->dest];
        h[1] = max(h[1], h[0] + max(f[j->dest][0], f[j->dest][1]) + tag[i]);
        h[0] += g[j->dest];
    }
    f[i][3] = h[3];
    g[i] = max(max(f[i][0], f[i][1]), max(f[i][2], f[i][3]));
}

int main() {
    #ifdef LOCAL_JUDGE
    freopen("in.txt", "r", stdin);
    #endif
    while (scanf("%d %d", &n, &m), n || m) {
        EP = EdgePool;
        memset(e, 0, sizeof(e));
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        memset(tag, 0, sizeof(tag));

        for (int i = 1; i <= n; i++) {
            scanf("%d", &parent[i]);
            if (parent[i]) {
                addedge(parent[i], i);
            }
        }
        for (int i = 1; i <= m; i++) {
            int x;
            scanf("%d", &x);
            tag[x] = 1;
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (parent[i] == 0) {
                dp(i);
                ans += g[i];
            }
        }
        printf("%d
", ans);
    }

    return 0;
}