전략 게임(문제 해결 트리 DP)

처음 트리 DP를 씁니다.

있는 것도 있고 없는 것도 있다

트리 DP에서 DP의 "단계"는 일반적으로 깊이에서 얕은(하위 트리가 작은 것부터 큰 것까지) 순서로 사용됩니다.
대부분의 경우 우리는 귀속 방식을 이용하여 트리 DP를 실현한다. 각 노드 x에 대해 우리는 먼저 그의 하위 노드를 귀속시키고 거슬러 올라갈 때 하위 노드에서 노드 x로 이동한다.
이 물 넘치는 나무 DP 한번 봅시다.

제목 설명

Bob은 컴퓨터 게임, 특히 전략 게임을 좋아한다.하지만 그는 게임을 빨리 할 수 있는 방법을 자주 찾지 못한다.지금 그에게 문제가 하나 있다.그는 옛 성곽을 세우려고 하는데, 성곽 안의 길이 나무 한 그루를 형성하려고 한다.그는 이 나무의 결점에 최소한의 병사들을 놓아서 이 병사들이 모든 길을 볼 수 있도록 하려고 한다.한 병사가 결점에 있을 때 결점과 연결된 모든 변이 보일 수 있으니 주의해라.
프로그램을 짜서 나무를 정해서 밥이 최소한의 병사를 배치해야 한다는 것을 계산해 주세요.

입력 형식

입력 파일의 데이터는 트리를 나타냅니다. 첫 번째 줄 N은 트리의 결점 수를 나타냅니다.두 번째 줄에서 N+1 줄까지 각 결점 정보를 설명한다. 순서는 다음과 같다. 이 결점 표지 i, k(뒤에 k변이 결점 I와 연결된다), 다음 k개수는 각각 각 변의 다른 결점 표지 r1, r2,..., rk이다.n (0)

출력 형식

출력 파일은 최소한의 병사 수를 위한 숫자만 포함합니다.

샘플 데이터

input 4 0 1 1 1 2 2 3 2 0 3 0
output
1

Solution

f[i][0/1] f[i][0/1]는 i가 가장 적은 병사 수를 뽑았는지 여부를 나타낸다.

 //By Bibi
///                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
///             __.'              ~.   .~              `.__
///           .'//                  \./                  \\`.
///        .'//                     |                     \\`.
///       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
///     .'//.-"                 `-.  |  .-'                 "-.\\`.
///   .'//______.============-..   \ | /   ..-============.______\\`.
/// .'______________________________\|/______________________________`.
#include
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int MAXN=1501;
int inline read(){
    int sum=0,flag=1;
    char c;
    for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;
    for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';
    return sum*flag;
}
int n;
struct edge{
    int y,next;
}e[MAXN<<1];
int f[MAXN][2];
int link[MAXN];
int tot;
int num[MAXN];
void inline insert(int x,int y){
    e[++tot].y=y;e[tot].next=link[x];link[x]=tot;
}
void inline init(){
    n=read();
    int x,y;
    rep(i,1,n){
        x=read();
        num[x]=read();
        rep(j,1,num[x]){
            y=read();
            insert(x,y);
            insert(y,x);
        }
    }
}
void inline DP(int x,int fa){
    f[x][1]=1;
    for(int i=link[x];i;i=e[i].next){
        int y=e[i].y;
        if(y==fa) continue;
        DP(y,x);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][0],f[y][1]);
    }
}
int main(){
    init();
    DP(0,-1);
    printf("%d",min(f[0][0],f[0][1]));
    return 0;
}