uvalive2038(트리 DP 베이스)

제목의 대의: 나무 한 그루를 정하고 가능한 한 적은 점을 선택해야 선택되지 않은 점은 적어도 선택한 점과 인접할 수 있다.
사고방식: 트리 DP.01 가방 문제와 유사합니다.나무의 결점은 선택하든지 말든지.dp[i][0]는 i번째 결점을 선택하지 않는다는 뜻이다. 그러면 dp[i][0]+= dp[j][1]. 그 중에서 j는 i의 하위 나무의 뿌리 노드이다.dp[i][1]는 i번째 결점을 선택해야 한다는 뜻이다. 그러면 dp[i][1]+=min(dp[j][1], dp[j][0])
질문 하나 발견: 9 0: (3) 1 2 3 2: (1) 4 4: (1) 5 5: (3) 6 7 8 이 데이터의 답은 2인데 튀어나온 것은 3이다.몰라요.코드:

#include <iostream>
using namespace std;
#include <cstring>
#include <cstdio>
const int maxn = 1510;
int n;
char str[120];
int tot;
int head[maxn];
int d[maxn][3];
struct Edge {
    int t,ne;
}edge[maxn *(maxn - 1)/2];

void addedge(int u,int v) {
    edge[tot].t = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
void dfs(int u,int father) {
    d[u][0] = 0;
    d[u][1] = 1;
    for(int e = head[u];e != - 1; e = edge[e].ne) {
        int v = edge[e].t;
        if(v == father)
            continue;
        dfs(v,u);
        d[u][0] += d[v][1];
        d[u][1] += min(d[v][0],d[v][1]);
    }
}
int main() {

    while(scanf("%d",&n) !=EOF) {
        tot = 0;
        memset(head,-1,sizeof(head));
        for(int i = 0; i < n ; i++) {
            scanf("%s",str);
            int flag = 0;
            int start,num;
            int e;
            for(int j = 0; str[j]!= '\0';) {
                if(str[j] >= '0' && str[j] <= '9') {
                    int temp = str[j] - '0';
                    j++;
                    while(str[j] >= '0' && str[j] <= '9') {
                        temp = temp * 10 + (str[j] - '0');
                        j++;
                    }
                    if(flag == 0) {
                        start = temp;
                        flag ++;
                    }
                    else 
                        num = temp;
                }
                else 
                    j++;
            }
            for(int j = 0; j < num; j++) {
                scanf("%d",&e);
                addedge(start,e);
                addedge(e,start);
            }
        }
        dfs(0,-1);
        printf("%d
",min(d[0][0],d[0][1]));
    }

    return 0;
}